Injection-locked laser network for solving NP-complete problems
Abstract/Contents
- Abstract
- NP(Nondeterministic Polynomial)-complete problems are of great interest in various scientific and engineering fields. Although no algorithm has been found so far to find exact solutions to NP-complete problems efficiently, many have been discovered to search for approximate solutions in polynomial time. Quantum computation can solve problems such as factorization efficiently. However, it still requires exponential time to solve NP-complete problems because it is limited by various theoretical and practical factors, especially the requirement of a closed unitary system. This dissertation proposes a novel machine, based on an injection-locked laser network, which is capable of solving NP-complete Ising problems faster and more accurately. A proposed machine contains one master laser and M slave lasers, and implements the Ising Hamiltonian of M spins by injection from the master laser and mutual injection among slave lasers. For many Ising problems, the laser network spontaneously finds the polarization configuration with the minimum gain and loss, which is the ground state of the Ising Hamiltonian. The population of the excited states is depleted exponentially due to their finite loss difference to the ground state. The so-called minimum gain principle is confirmed both theoretically and numerically. Since the laser network operates in a highly dissipative system, it is more robust against noise and loss and more efficient compared to quantum computers which rely on a closed unitary system. Further research reveals that the injection-locked laser network has difficulties in solving Ising problems of larger scales that contain frustrated spin configurations and degenerate ground states. Because the readouts of the spin values are continuous rather than discrete variables, a false loss landscape is created in the evolution departing from the correct loss landscape generated by the desired Ising Hamiltonian. Subsequently, the minimum gain principle erroneously drives the laser network to the incorrect minimum of the false loss landscape. A self-learning algorithm is introduced to address the false loss landscape. In each iteration we execute four techniques to predict the correct configurations of problematic spins and enhance the signal-to-noise ratios. We instruct the laser network according to the predictions and enhancements, and then evolve the system until steady state is achieved to verify whether it follows the instructions self-consistently. Finally, the self-learning injection-locked laser network exhibits significantly better performance than existing algorithms based on the benchmark results for two NP-complete subsets of the Ising problems. The laser network can solve all Ising problems on cubic graphs of up to 20 spins with a small increase in time and finite success probability. The laser network can further obtain better solutions in much shorter times than the state-of-the-art approximation algorithm in solving the two-layer lattice problems of up to 800 spins.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2012 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Wen, Kai |
|---|---|
| Associated with | Stanford University, Department of Electrical Engineering |
| Primary advisor | Yamamoto, Yoshihisa |
| Thesis advisor | Yamamoto, Yoshihisa |
| Thesis advisor | Fisher, Daniel S |
| Thesis advisor | Mabuchi, Hideo |
| Advisor | Fisher, Daniel S |
| Advisor | Mabuchi, Hideo |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Kai Wen. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2012. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2012 by Kai Wen
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...