REPORTS

Cite as: P. L. McMahon et al., Science
10.1126/science.aah5178 (2016).

A fully-programmable 100-spin coherent Ising machinewith all-to-all connectionsPeter L. McMahon,1,2*† Alireza Marandi,1*† Yoshitaka Haribara,2,3,4 Ryan Hamerly,1 Carsten Langrock,1 Shuhei Tamate,2 Takahiro Inagaki,5Hiroki Takesue,5 Shoko Utsunomiya,2 Kazuyuki Aihara,3,4 Robert L. Byer,1 M. M. Fejer,1 Hideo Mabuchi,1 Yoshihisa Yamamoto1,6
1

E. L. Ginzton Laboratory, Stanford University, Stanford, CA 94305, USA. 2National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan.
Department of Mathematical Informatics, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113-8656, Japan. 4Institute of Industrial Science, The University of Tokyo, 46-1 Komaba, Meguro-ku, Tokyo 153-8505, Japan. 5NTT Basic Research Laboratories, 3-1 Morinosato, Wakamiya, Atsugi, Kanagawa 243-0198, Japan. 6ImPACT Program,
Japan Science and Technology Agency, Gobancho 7, Chiyoda-ku, Tokyo 102-0076, Japan.
†These authors contributed equally to this work.

*Corresponding author. E-mail: pmcmahon@stanford.edu (P.L.M.); marandi@stanford.edu (A.M.)

Unconventional, special-purpose machines may aid in accelerating the solution of some of the hardest
problems in computing, such as large-scale combinatorial optimizations, by exploiting different operating
mechanisms than standard digital computers. We present a scalable optical processor with electronic
feedback that can be realized at large scale with room-temperature technology. Our prototype machine isable to find exact solutions of, or to sample good approximate solutions to, a variety of hard instances ofIsing problems with up to 100 spins and 10,000 spin-spin connections.
Combinatorial optimization problems, including many NPhard problems, are central in numerous important application areas, including operations and scheduling, drug discovery, finance, circuit design, sensing, and manufacturing.
Despite large advances in both algorithms and digital computer technology, even typical instances of NP-hard problems that arise in practice may be very difficult to solve on
conventional computers. There is a long history of attempts
to find alternatives to current von-Neumann-computerbased methods for solving such problems, including usingneural networks realized with analog electronic circuits (1,2) and using molecular computing (3–5). Both lines of investigation continue to inspire related work (6, 7). A major topic of contemporary interest is the study of adiabatic
quantum computation (AQC) (8) and quantum annealing(QA) (9, 10). Sophisticated AQC/QA devices are already under study (11–14), but providing dense connectivity between
qubits remains a major challenge (15) with important implications for the efficiency of AQC/QA systems (16).
Networks of coupled optical parametric oscillators(OPOs) are an alternative physical system, with an unconventional operating mechanism (17–20), for solving the Ising
problem (21, 22), and by extension many other combinatorial optimization problems (23). Formally, the N-spin Ising
problem is to find the configuration of spins σ i ∈ {−1, +1} (i= 1, ..., N) that minimizes the energy function
H = − ∑ J ijσ iσ j ∑ hiσ i , where the particular problem
1≤ i < j ≤ N

1≤ i ≤ N

instance being solved is specified by the N × N matrix J(with elements Jij) and the length-N vector h (with elements
hi).
First release: 20 October 2016

We have realized a system with a scalable architecturethat uses measurement-feedback in place of a network of
optical delay lines (which were used in initial, lowconnectivity, non-reprogrammable demonstrations of theconcept (18, 24, 25)). Our 100-spin Ising machine allows
connections between any spin and any other spin, and isfully programmable. We show that measurement-feedbackbased OPO Ising machines can solve many different Ising
problems, and in cases where exact solutions are not easy toobtain, we can find good approximate solutions.
The schematic of our experimental setup (Fig. 1) showsthat our Ising machine is formed by the combination oftime-division-multiplexed OPOs (18) in a single fiber-ringcavity, with measurement and feedback (injection) stages
that act to couple the pulses in the cavity such that the Ising
Hamiltonian is realized. Details are provided in the Supplementary Materials (26).
We have focused our experiments on Ising problems onundirected, unweighted graphs (V (vertices), E (edges)),
where Jij = –1 when Spin i and Spin j are connected, and Jij= 0 otherwise, and for which the linear (Zeeman) terms hi
are zero. An Ising problem of this form is equivalent to the
MAX-CUT problem on the underlying graph (17). MAX-CUT
is the problem of partitioning the vertices of a graph into
two disjoint subsets such that the number of edges between
the two subsets is maximized; the partition is called a cut.
MAX-CUT remains NP-hard even when the input is restricted to unweighted cubic graphs (27). We refer interchangeably to the MAX-CUT problem and to the Ising problem, andthe solutions thereof. The energy of a particular spin configuration {σi}i=1,...,N for an Ising problem is given bywww.sciencemag.org(Page numbers not final at time of first release) 1

Downloaded from http://science.sciencemag.org/ on November 23, 20163

1≤ i < j ≤ N

1≤ i ≤ N

represents
a
cut
of
size
{σi}
1
1
C ({σ i } ) =−∑ J ij − 2 H ({σ i }) ; i.e., there is a direct
2 1≤i < j ≤ Nmapping between the energies in the Ising problem and thecut sizes in the MAX-CUT problem, and we note that minimizing the Ising energy maximizes the cut.
Figure 2A shows the unweighted, undirected Möbius
Ladder (cubic) graph with N = 16 vertices. We programmed
the corresponding J matrix into our feedback electronics,
and ran the problem on our experimental apparatus. Figure
2B shows, from a single run of this single problem instance,
the evolution of the in-phase component of each OPO pulse(ci) as a function of the number of times each pulse circulated around the cavity (the number of roundtrips). The computation time is given by Tcomp = TrtNrt, where Trt = 1.6 μs is
the single roundtrip time and Nrt is the number of roundtrips. Each spin σi in the Ising problem is represented by asingle OPO pulse; if the in-phase component ci of the ith
OPO pulse is less than zero, i.e., ci < 0, we make the spin
assignment σi = –1, and if the in-phase component is greaterthan zero, i.e., ci > 0, we make the spin assignment σi = +1.
As the feedback signal level is gradually increased, the OPO
amplitudes increase. Most of the OPOs obtain their ultimate
signs by Roundtrip 60. By Roundtrip 100, all the OPOs havereached a steady state. Figure 2C shows the graph cut size,or equivalently the Ising energy, represented by the spin
configuration after each roundtrip for the run shown in Fig.
2B. We see that the system evolves toward solutions representing larger graph cuts, or equivalently lower Ising energies, and the steady-state configuration is that of a groundstate. The system finds the ground state within 120 μs. If wererun the computation many times, we find that our system
always returns the optimal solution for this particular problem instance (Fig. 2D). Figure 2, E and F, shows the distributions of obtained solutions for two other N = 16 cubic
graphs. In both cases the system finds the ground state in alarge fraction of the runs, and when the system does not
return a ground state, it returns a state that has energy
close to that of the ground state, i.e., a good approximate
solution. To illustrate that these instances are not special
cases for which the Ising machine finds exact solutions(ground states), we attempted to solve all possible problem
instances of N = 16 cubic graphs, of which there are 4060.
Figure 2G shows that we were able to find ground stateswith probability greater than 20% for every single instance.
In this experiment, and all that follow, every run was set toproceed for Nrt = 300 roundtrips, i.e., a computation time of
Tcomp = 480 μs.
rationFirst release: 20 October 2016

We next explored how the Ising machine performs as afunction of the size of the problem. In this first scaling
study, we used the Möbius Ladder graphs with varying size.
This is a convenient choice as there is a closed-form solution
for the maximum cut and Ising energy for every instance inthis family of graphs. The Möbius Ladder graphs with N = 8,
12, ..., 100 were solved (Fig. 3A). For each instance we performed multiple sets of 100 runs. Each 100-run set resulted
in a solution-energy histogram (Fig. 3B shows an example
for N = 8). Note that for the runs in which the ground state
is not found, the system again finds good approximate solutions (Fig. 3, C and D).
To understand how the performance of our system scales
as a function of problem size for more general problems, 10
random instances of cubic graphs were generated for eachgraph size N = 10, 20, ..., 100, and each instance run on ourapparatus. Figure 4A shows the success probabilities foreach instance, aggregated by graph size. In contrast to theprevious results, not only the probability of obtaining aground state, but also the probability of obtaining a solutionthat is within x% of the optimal (maximum cut) solution isshown. The error bars indicate a spread in success probabilities primarily due to the fact that different random instances of each size may be more or less difficult to solve.
Figure 4B shows, for each graph size, the total computation time required to obtain a solution with the given accuracy with probability 99% within that time, and is derived
directly from Fig. 4A. The total time is given by Tcomp × log(1– 0.99)/log(1 – ps), where ps is the corresponding successprobability from Fig. 4A. The total computation time required to obtain ground states (100% accuracy) grows rapidly with problem size N, although it is still small in absoluteterms for N = 100: less than 200 ms. The growth in total
computation time is far less severe when the required solution accuracy is reduced: for 95% accuracy, the required
time increases from approximately 1 ms when N = 10 to approximately 4 ms when N = 100; for 90% accuracy, the required time remains roughly constant at approximately 1
ms.
Figure 4, C and D, shows the OPO amplitudes and cut
sizes/energies, respectively, as a function of the number ofroundtrips for a single run on a single non-regular randomgraph instance with N = 100 vertices and E = 495 edges.
We see that the global optimum is reached within 100 μs,
and the system reaches a steady state after approximately
120 μs. This graph instance is one of 10 instances that weregenerated having 495 edges. We generated 10 randomgraphs with a fixed number of edges, for each of
E = 50, 495,990,1485,1980, 2475, 2970,3465,3960, 4455, 4900 ,and ran these instances on our apparatus. Figure 4E shows
the results of this study of the performance on random

www.sciencemag.org(Page numbers not final at time of first release)2

Downloaded from http://science.sciencemag.org/ on November 23, 2016

− ∑ J ijσ iσ j − ∑ hiσ i . The same spin configuH ({σ i } ) =REFERENCES AND NOTES
1. J. J. Hopfield, D. W. Tank, Computing with neural circuits: A model. Science 233,
625–633 (1986). Medline doi:10.1126/science.3755256
2. D. Tank, J. Hopfield, Simple ‘neural’ optimization networks: An A/D converter,
signal decision circuit, and a linear programming circuit. IEEE Trans. Circ. Syst.
33, 533–541 (1986). doi:10.1109/TCS.1986.1085953
3. L. M. Adleman, Molecular computation of solutions to combinatorial problems.
Science 266, 1021–1024 (1994). Medline doi:10.1126/science.7973651
4. R. J. Lipton, DNA solution of hard computational problems. Science 268, 542–545(1995). Medline doi:10.1126/science.7725098
5. R. S. Braich, N. Chelyapov, C. Johnson, P. W. K. Rothemund, L. Adleman, Solutionof a 20-variable 3-SAT problem on a DNA computer. Science 296, 499–502(2002). Medline doi:10.1126/science.1069528
6. M. Ercsey-Ravasz, Z. Toroczkai, Optimization hardness as transient chaos in an
analog approach to constraint satisfaction. Nat. Phys. 7, 966–970 (2011).
doi:10.1038/nphys2105
7. L. Qian, E. Winfree, J. Bruck, Neural network computation with DNA strand
displacement cascades. Nature 475, 368–372 (2011). Medline
doi:10.1038/nature10262
8. E. Farhi, J. Goldstone, S. Gutmann, J. Lapan, A. Lundgren, D. Preda, A quantum
adiabatic evolution algorithm applied to random instances of an NP-complete
problem. Science 292, 472–475 (2001). Medline doi:10.1126/science.1057726
9. T. Kadowaki, H. Nishimori, Quantum annealing in the transverse Ising model. Phys.
Rev. E Stat. Phys. Plasmas Fluids Relat. Interdiscip. Topics 58, 5355–5363(1998).
doi:10.1103/PhysRevE.58.5355
10. J. Brooke, D. Bitko, T. F. Rosenbaum, G. Aeppli, Quantum annealing of adisorderedmagnet.
Science284,
779–781(1999).
Medlinedoi:10.1126/science.284.5415.779
11. M. W. Johnson, M. H. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris,
A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K.

First release: 20 October 2016

Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E.
Tolkacheva, C. J. Truncik, S. Uchaikin, J. Wang, B. Wilson, G. Rose, Quantum
annealing with manufactured spins. Nature 473, 194–198 (2011). Medline
doi:10.1038/nature10012
12. T. F. Rønnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D.
A. Lidar, M. Troyer, Defining and detecting quantum speedup. Science 345, 420–424 (2014). Medline doi:10.1126/science.1252319
13. S. Boixo, T. F. Rønnow, S. V. Isakov, Z. Wang, D. Wecker, D. A. Lidar, J. M.
Martinis, M. Troyer, Evidence for quantum annealing with more than one
hundred qubits. Nat. Phys. 10, 218–224 (2014). doi:10.1038/nphys2900
14. R. Barends, A. Shabani, L. Lamata, J. Kelly, A. Mezzacapo, U. Las Heras, R.
Babbush, A. G. Fowler, B. Campbell, Y. Chen, Z. Chen, B. Chiaro, A. Dunsworth, E.
Jeffrey, E. Lucero, A. Megrant, J. Y. Mutus, M. Neeley, C. Neill, P. J. O’Malley, C.
Quintana, P. Roushan, D. Sank, A. Vainsencher, J. Wenner, T. C. White, E. Solano,
H. Neven, J. M. Martinis, Digitized adiabatic quantum computing with asuperconducting circuit. Nature 534, 222–226 (2016). Medline
doi:10.1038/nature17658
15. P. I. Bunyk, E. M. Hoskinson, M. W. Johnson, E. Tolkacheva, F. Altomare, A. J.
Berkley, R. Harris, J. P. Hilton, T. Lanting, A. J. Przybysz, J. Whittaker,
Architectural Considerations in the Design of a Superconducting Quantum
Annealing Processor. IEEE Trans. Appl. Supercond. 24, 1–10 (2014).
doi:10.1109/TASC.2014.2318294
16. E. G. Rieffel, D. Venturelli, B. O’Gorman, M. B. Do, E. M. Prystay, V. N.
Smelyanskiy, A case study in programming a quantum annealer for hard
operational planning problems. Quant. Inform. Process. 14, 1–36 (2014).
doi:10.1007/s11128-014-0892-x
17. Z. Wang, A. Marandi, K. Wen, R. L. Byer, Y. Yamamoto, Coherent Ising machine
based on degenerate optical parametric oscillators. Phys. Rev. A 88, 063853(2013). doi:10.1103/PhysRevA.88.063853
18. A. Marandi, Z. Wang, K. Takata, R. L. Byer, Y. Yamamoto, Network of timemultiplexed optical parametric oscillators as a coherent Ising machine. Nat.
Photonics 8, 937–942 (2014). doi:10.1038/nphoton.2014.249
19. K. Takata, A. Marandi, Y. Yamamoto, Quantum correlation in degenerate opticalparametric oscillators with mutual injections. Phys. Rev. A 92, 043821 (2015).
doi:10.1103/PhysRevA.92.043821
20. Y. Haribara, S. Utsunomiya, Y. Yamamoto, Computational Principle andPerformance Evaluation of Coherent Ising Machine Based on Degenerate OpticalParametric Oscillator Network. Entropy 18, 151 (2016). doi:10.3390/e18040151
21. F. Barahona, On the computational complexity of Ising spin glass models. J. Phys.
Math. Gen. 15, 3241–3253 (1982). doi:10.1088/0305-4470/15/10/028
22. S. Istrail, Proceedings of the Thirty-second Annual ACM Symposium on Theory ofComputing, STOC (2000), pp. 87–96.
23. A. Lucas, Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).
doi:10.3389/fphy.2014.00005
24. K. Takata et al., Sci. Rep. 6, 340897 (2016).
25. T. Inagaki, K. Inaba, R. Hamerly, K. Inoue, Y. Yamamoto, H. Takesue, Large-scale
Ising spin network based on degenerate optical parametric oscillators. Nat.
Photonics 10, 415–419 (2016). doi:10.1038/nphoton.2016.68
26. Materials and methods are available as supplementary materials on Science
Online.
27. M. R. Garey, D. S. Johnson, L. Stockmeyer, Some simplified NP-complete graphproblems. Theor. Comput. Sci. 1, 237–267 (1976). doi:10.1016/03043975(76)90059-1
28. J. Roslund, R. M. de Araújo, S. Jiang, C. Fabre, N. Treps, Wavelength-multiplexed
quantum networks with ultrafast frequency combs. Nat. Photonics 8, 109(2014). doi:10.1038/nphoton.2013.340
29. W. J. Munro, M. D. Reid, Transient macroscopic quantum superposition
states in degenerate parametric oscillation using squeezed reservoir fields. Phys.
Rev. A 52, 2388 (1995). doi:10.1103/PhysRevA.52.2388
30. K. R. Motes, A. Gilchrist, J. P. Dowling, P. P. Rohde, Scalable boson sampling with
time-bin encoding using a loop-based architecture. Phys. Rev. Lett. 113, 120501(2014). Medline doi:10.1103/PhysRevLett.113.120501
31. M. Denil, N. de Freitas, NIPS Deep Learning and Unsupervised Feature Learning
Workshop (2011).

www.sciencemag.org(Page numbers not final at time of first release)3

Downloaded from http://science.sciencemag.org/ on November 23, 2016

graphs as a function of edge
density d 2 E  V ( V − 1)  ;=the system was able to find good solutions for all the attempted densities.
OPO Ising machines have the potential to harness anumber of quantum features, including squeezing and superposition (20). Pulsed OPOs already have a substantial
quantum-mechanical nature (28), and networks of OPOs
can generate spatial multimode entanglement (19). The experimental system reported in this work is well-described bya quantum-mechanical model (20) (with very good agreement between our experimental results and numerical simulation results (26)). However, the extent to which classicalmodels can capture the behavior of OPO Ising machines is
not yet known, and follow-up studies are needed to determine the fundamental computational power of OPO Isingmachines. Two future modifications to the experiment that
could increase the relevance of quantum mechanics are reducing the cavity round-trip loss, and injecting squeezed
vacuum states into the open port of the measurement
beamsplitter (29), which is predicted to improve the successprobability (26).
While we find the overall direction of OPO Ising machines promising, the techniques we have demonstrated are
not necessarily restricted to OPO Ising machines, and photonic-AQC and boson-sampling (30) experiments, amongst
others, may be able to adapt our methods.

First release: 20 October 2016

ACKNOWLEDGMENTS
This research was funded by the Impulsing Paradigm Change through Disruptive
Technologies (ImPACT) Program of the Council of Science, Technology andInnovation (Cabinet Office, Government of Japan). PLM was partially supported
by a Stanford Nano- and Quantum Science and Engineering Postdoctoral
Fellowship. We thank Ken Leedle, Andrew Ceballos, Kai Wen and Zhe Wang fortechnical assistance, and Michel Digonnet, Brian Lantz, Tatsuhiro Onodera,
Edwin Ng, Timothee Leleu, Charles Limouse, Dodd Gray, Gil Tabak and Nikolas
Tezak for helpful discussions.
SUPPLEMENTARY MATERIALS
www.sciencemag.org/cgi/content/full/science.aah5178/DC1
Materials and Methods
Supplementary Text
Figs. S1 to S5
References (31–58)

Downloaded from http://science.sciencemag.org/ on November 23, 201632. V. Dumoulin, I. J. Goodfellow, A. Courville, Y. Bengio, arXiv:1312.5258 (2013).
33. F. Rendl, G. Rinaldi, A. Wiegele, Solving Max-Cut to optimality by intersecting
semidefinite and polyhedral relaxations. Math. Program. 121, 307–335 (2008).
doi:10.1007/s10107-008-0235-8
34. U. Benlic, J.-K. Hao, Breakout Local Search for the Max-Cutproblem. Eng. Appl.
Artif. Intell. 26, 1162–1173 (2013). doi:10.1016/j.engappai.2012.09.001
35. S. W. Shin, G. Smith, J. A. Smolin, U. Vazirani, arXiv:1401.7087 (2014).
36. A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, A. Aspuru-Guzik, Finding
low-energy conformations of lattice protein models by quantum annealing. Sci.
Rep. 2, 571 (2012). Medline doi:10.1038/srep00571
37. C. C. McGeoch, C. Wang, Proceedings of the ACM International Conference on
Computing Frontiers, CF ’13 (ACM, New York, NY, USA, 2013), pp. 23:1–23:11.
38. D. Venturelli et al., Phys. Rev. X 5, 031040 (2015).
39. D. Venturelli, D. J. J. Marchand, G. Rojo, arXiv:1506.08479 (2015).
40. V. S. Denchev et al., arXiv:1512.02206 (2015).
41. Z. Bian et al., arXiv:1603.03111 (2016).
42. S. Mandra, Z. Zhu, W. Wang, A. Perdomo-Ortiz, H. G. Katzgraber,
arXiv:1604.01746 (2016).
43. D. Maruo, S. Utsunomiya, Y. Yamamoto, Truncated Wigner theory of coherent
Ising machines based on degenerate optical parametric oscillator network. Phys.
Scr. 91, 083010 (2016). doi:10.1088/0031-8949/91/8/083010
44. R. Hamerly et al., arXiv:1605.08121 (2016).
45. D. F. Walls, G. J. Milburn, Quantum Optics (Springer-Verlag, Berlin, 2008),
second edn.
46. D. T. Pegg, S. M. Barnett, J. Mod. Opt. 44, 225 (1997).
47. P. Alimonti, V. Kann, Algorithms and Complexity, G. Bongiovanni, D. P. Bovet, G.
D. Battista, eds., no. 1203 in Lecture Notes in Computer Science (Springer Berlin
Heidelberg, 1997), pp. 288–298. DOI: 10.1007/3-540-62592-5_80.
48. J. Sima, S. E. Schaeffer, arXiv:cs/0506100 (2005).
49. B. Bollobás, A Probabilistic Proof of an Asymptotic Formula for the Number ofLabelled Regular Graphs. Eur. J. Combin. 1, 311–316 (1980). doi:10.1016/S01956698(80)80030-8
50. N. C. Wormald, Surveys in combinatorics, J. D. Lamb, D. A. Preece, eds., London
Math. Soc. Lecture Note Series (Canterbury, 1999), pp. 239–298.
51. G. Bounova, Topological evolution of networks: case studies in the US airlines andlanguage Wikipedias, Ph.D. Thesis, Massachusetts Institute of Technology(2009).
52. M. Yamaoka et al., 2015 IEEE International Solid-State Circuits Conference(ISSCC) (2015), pp. 1–3.
53. Y. Okawachi, M. Yu, K. Luke, D. O. Carvalho, S. Ramelow, A. Farsi, M. Lipson, A. L.
Gaeta, Dual-pumped degenerate Kerr oscillator in a silicon nitride
microresonator.
Opt.
Lett.
40,
5267–5270(2015).
Medlinedoi:10.1364/OL.40.005267
54. P. C. Humphreys, B. J. Metcalf, J. B. Spring, M. Moore, X. M. Jin, M. Barbieri, W. S.
Kolthammer, I. A. Walmsley, Linear optical quantum computing in a single spatial
mode.
Phys.
Rev.
Lett.
111,
150501(2013).
Medlinedoi:10.1103/PhysRevLett.111.150501
55. S. Aaronson, A. Arkhipov, Proceedings of the Forty-third Annual ACM Symposiumon Theory of Computing, STOC ’11 (ACM, New York, NY, USA, 2011), pp. 333–
342.
56. Y. He et al., arXiv:1603.04127 (2016).
57. J. Huh, G. G. Guerreschi, B. Peropadre, J. R. McClean, A. Aspuru-Guzik, Boson
sampling for molecular vibronic spectra. Nat. Photonics 9, 615–620 (2015).
doi:10.1038/nphoton.2015.153
58. U. L. Andersen, T. Gehring, C. Marquardt, G. Leuchs, 30 years of squeezed light
generation. Phys. Scr. 91, 053001 (2016). doi:10.1088/00318949/91/5/053001

8 July 2016; accepted 26 September 2016
Published online 20 October 201610.1126/science.aah5178

www.sciencemag.org(Page numbers not final at time of first release)4

First release: 20 October 2016www.sciencemag.org(Page numbers not final at time of first release)

Downloaded from http://science.sciencemag.org/ on November 23, 2016

Fig. 1. Experimental schematic of ameasurement-feedback-based
coherent Ising machine. A time-divisionmultiplexed pulsed degenerate opticalparametric oscillator is formed by anonlinear crystal (PPLN) in a fiber ringcavity containing 160 pulses. A fraction ofeach pulse is measured and used tocompute a feedback signal that effectively
couples the otherwise-independent pulses
in the cavity. IM: intensity modulator; PM:phase modulator; LO: local oscillator;
SHG: second-harmonic generation; FPGA:
field-programmable gate array.

5

Downloaded from http://science.sciencemag.org/ on November 23, 2016

Fig. 2. Results with N = 16 cubic graphs. (A) A Möbius Ladder graph with N = 16 vertices. (B) The
evolution of the in-phase components ci of the N = 16 OPO pulses as a function of the computation
time. (C) The graph cut size achieved as a function of the computation time. (D to F) Histograms ofobtained solutions in 100 runs for the graphs shown in the insets. (G) Histogram of the observed
probabilities of obtaining a ground state in a single run, for all 4060 unweighted, undirected cubic
graphs with N = 16 vertices.

First release: 20 October 2016www.sciencemag.org(Page numbers not final at time of first release)6

Downloaded from http://science.sciencemag.org/ on November 23, 2016

Fig. 3. Results with various-size
Möbius Ladder graphs. (A)Observed probability of obtaininga ground state of the Möbius
Ladder graph in a single run, as afunction of the size N of the graph.
Multiple 100-run batches were
performed for each graph size toobtain the standard deviations,which are shown as error bars. (Bto D) Histograms of obtained
solutions in 100 runs for thegraphs shown in the insets.

First release: 20 October 2016www.sciencemag.org(Page numbers not final at time of first release)7

Downloaded from http://science.sciencemag.org/ on November 23, 2016

Fig. 4. Results with various-size and various-density random graphs. (A) Observed probability ofobtaining a solution whose cut size is at least x% of the global optimum (maximum cut), as a function ofgraph size N, for random cubic graph instances. Error bars indicate one standard deviation, which isdominated by the difference in difficulty between the various problem instances. (B) The runtime thatwould be required to obtain a solution of a particular accuracy with 99% probability. (C) The evolution of
the in-phase components ci of the N = 100 OPO pulses as a function of the computation time, for a single
run with the graph shown in the inset of Panel D. (D) The graph cut size achieved as a function of thecomputation time. Inset: the graph being solved. (E) Observed success probability of obtaining a solution
with a particular accuracy as a function of the density of edges in the graph. Experiments were
performed on randomly-generated N = 100-vertex graphs with fixed numbers of edges. Error bars
indicate one standard deviation.

First release: 20 October 2016www.sciencemag.org(Page numbers not final at time of first release)8A fully-programmable 100-spin coherent Ising machine withall-to-all connectionsPeter L. McMahon, Alireza Marandi, Yoshitaka Haribara, Ryan
Hamerly, Carsten Langrock, Shuhei Tamate, Takahiro Inagaki, Hiroki
Takesue, Shoko Utsunomiya, Kazuyuki Aihara, Robert L. Byer, M. M.
Fejer, Hideo Mabuchi and Yoshihisa Yamamoto (October 20, 2016)
published online October 20, 2016

This copy is for your personal, non-commercial use only.

Article Tools

Visit the online version of this article to access the personalization and article
tools:
http://science.sciencemag.org/content/early/2016/10/19/science.aah5178

Permissions

Obtain information about reproducing this article:
http://www.sciencemag.org/about/permissions.dtl

Science (print ISSN 0036-8075; online ISSN 1095-9203) is published weekly, except the last week inDecember, by the American Association for the Advancement of Science, 1200 New York Avenue NW,
Washington, DC 20005. Copyright 2016 by the American Association for the Advancement of Science;
all rights reserved. The title Science is a registered trademark of AAAS.

Downloaded from http://science.sciencemag.org/ on November 23, 2016

Editor's Summary