A Quantum N-Queens Solver

Valentin Torggler1, Philipp Aumann1, Helmut Ritsch1, and Wolfgang Lechner1,2

1Institute for Theoretical Physics, University of Innsbruck, A-6020 Innsbruck, Austria
2Institute for Quantum Optics and Quantum Information of the Austrian Academy of Sciences, A-6020 Innsbruck, Austria

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

The $N$-queens problem is to find the position of $N$ queens on an $N$ by $N$ chess board such that no queens attack each other. The excluded diagonals $N$-queens problem is a variation where queens cannot be placed on some predefined fields along diagonals. This variation is proven NP-complete and the parameter regime to generate hard instances that are intractable with current classical algorithms is known. We propose a special purpose quantum simulator that implements the excluded diagonals $N$-queens completion problem using atoms in an optical lattice and cavity-mediated long-range interactions. Our implementation has no overhead from the embedding allowing to directly probe for a possible quantum advantage in near term devices for optimization problems.

Solving puzzles can be a difficult task even for the fastest digital computers. A generic example already studied by the famous mathematician Gauss is the so-called N-queens problem. The task is to find all possibilities to place N queens on an NxN chess board, such that they cannot attack each other according to chess rules. Recently it was shown that variations of the problem with extra constraints are not solvable with classical algorithms within reasonable time.

In the last decades the idea emerged that special purpose quantum computers might find a solution faster. However, whether quantum effects can indeed speed up such calculations is still an open question and thus it is crucial to provide experimental possibilities to gauge an advantages of quantum computing.

In this work we propose a special purpose analog computer serving as a test bed to study speedup for the N-queens problem in the quantum regime. The idea is to build a miniaturized chess board from atoms and light at nearly zero temperature, where the rules of quantum mechanics apply. Ultra-cold atoms moving via quantum tunneling in a lattice created by laser light, take the role of the queens on the chess board. The chess rules are imposed by placing the atoms in an optical resonator and shining in specially structured light. Due to the one-to-one natural design of the experiment there is no overhead in atoms and fairly small system sizes are sufficient to enter the classically intractable regime.

► BibTeX data

► References

[1] Aram W Harrow and Ashley Montanaro. Quantum computational supremacy. Nature, 549 (7671): 203-209, 2017. 10.1038/​nature23458.
https:/​/​doi.org/​10.1038/​nature23458

[2] J Ignacio Cirac and Peter Zoller. Goals and opportunities in quantum simulation. Nat. Phys., 8 (4): 264-266, apr 2012. ISSN 1745-2473. 10.1038/​nphys2275.
https:/​/​doi.org/​10.1038/​nphys2275

[3] Rainer Blatt and Christian F Roos. Quantum simulations with trapped ions. Nature Physics, 8 (4): 277-284, 2012. 10.1038/​nphys2252.
https:/​/​doi.org/​10.1038/​nphys2252

[4] Immanuel Bloch, Jean Dalibard, and Sylvain Nascimbene. Quantum simulations with ultracold quantum gases. Nat. Phys., 8 (4): 267-276, apr 2012. ISSN 1745-2473. 10.1038/​nphys2259.
https:/​/​doi.org/​10.1038/​nphys2259

[5] Alán Aspuru-Guzik and Philip Walther. Photonic quantum simulators. Nature Physics, 8 (4): 285-291, 2012. 10.1038/​nphys2253.
https:/​/​doi.org/​10.1038/​nphys2253

[6] Sylvain De Léséleuc, Sebastian Weber, Vincent Lienhard, Daniel Barredo, Hans Peter Büchler, Thierry Lahaye, and Antoine Browaeys. Accurate mapping of multilevel rydberg atoms on interacting spin-1/​2 particles for the quantum simulation of ising models. Physical review letters, 120 (11): 113602, 2018. 10.1103/​PhysRevLett.120.113602.
https:/​/​doi.org/​10.1103/​PhysRevLett.120.113602

[7] Andrew A Houck, Hakan E Türeci, and Jens Koch. On-chip quantum simulation with superconducting circuits. Nature Physics, 8 (4): 292-299, 2012. 10.1038/​nphys2251.
https:/​/​doi.org/​10.1038/​nphys2251

[8] I. M. Georgescu, S. Ashhab, and Franco Nori. Quantum simulation. Rev. Mod. Phys., 86: 153-185, Mar 2014. 10.1103/​RevModPhys.86.153.
https:/​/​doi.org/​10.1103/​RevModPhys.86.153

[9] Mark Saffman. Quantum computing with atomic qubits and rydberg interactions: progress and challenges. Journal of Physics B: Atomic, Molecular and Optical Physics, 49 (20): 202001, 2016. 10.1088/​0953-4075/​49/​20/​202001.
https:/​/​doi.org/​10.1088/​0953-4075/​49/​20/​202001

[10] John Preskill. Quantum computing in the nisq era and beyond. Quantum, 2: 79, 2018. 10.22331/​q-2018-08-06-79.
https:/​/​doi.org/​10.22331/​q-2018-08-06-79

[11] Sergio Boixo, Sergei V Isakov, Vadim N Smelyanskiy, Ryan Babbush, Nan Ding, Zhang Jiang, Michael J Bremner, John M Martinis, and Hartmut Neven. Characterizing quantum supremacy in near-term devices. Nature Physics, 14 (6): 595, 2018. 10.1038/​s41567-018-0124-x.
https:/​/​doi.org/​10.1038/​s41567-018-0124-x

[12] John Preskill. Quantum computing and the entanglement frontier. arXiv:1203.5813 [quant-ph], 2012.
arXiv:1203.5813

[13] Hannes Bernien, Sylvain Schwartz, Alexander Keesling, Harry Levine, Ahmed Omran, Hannes Pichler, Soonwon Choi, Alexander S Zibrov, Manuel Endres, Markus Greiner, et al. Probing many-body dynamics on a 51-atom quantum simulator. Nature, 551 (7682): 579, 2017. 10.1038/​nature24622.
https:/​/​doi.org/​10.1038/​nature24622

[14] Kihwan Kim, M-S Chang, Simcha Korenblit, Rajibul Islam, Emily E Edwards, James K Freericks, G-D Lin, L-M Duan, and Christopher Monroe. Quantum simulation of frustrated ising spins with trapped ions. Nature, 465 (7298): 590-593, 2010. 10.1038/​nature09071.
https:/​/​doi.org/​10.1038/​nature09071

[15] Peter Schauß, Marc Cheneau, Manuel Endres, Takeshi Fukuhara, Sebastian Hild, Ahmed Omran, Thomas Pohl, Christian Gross, Stefan Kuhr, and Immanuel Bloch. Observation of spatially ordered structures in a two-dimensional rydberg gas. Nature, 491 (7422): 87-91, 2012. 10.1038/​nature11596.
https:/​/​doi.org/​10.1038/​nature11596

[16] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Phys. Rev. E, 58: 5355-5363, Nov 1998. 10.1103/​PhysRevE.58.5355.
https:/​/​doi.org/​10.1103/​PhysRevE.58.5355

[17] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. arXiv:quant-ph/​0001106, 2000.
arXiv:quant-ph/0001106

[18] Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90 (1): 015002, 2018. 10.1103/​RevModPhys.90.015002.
https:/​/​doi.org/​10.1103/​RevModPhys.90.015002

[19] Andrew Lucas. Ising formulations of many np problems. Frontiers in Physics, 2: 5, 2014. 10.3389/​fphy.2014.00005.
https:/​/​doi.org/​10.3389/​fphy.2014.00005

[20] Sergio Boixo, Troels F Rønnow, Sergei V Isakov, Zhihui Wang, David Wecker, Daniel A Lidar, John M Martinis, and Matthias Troyer. Evidence for quantum annealing with more than one hundred qubits. Nature Physics, 10 (3): 218, 2014. 10.1038/​nphys2900.
https:/​/​doi.org/​10.1038/​nphys2900

[21] Philipp Hauke, Helmut G Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D Oliver. Perspectives of quantum annealing: Methods and implementations. arXiv:1903.06559 [quant-ph], 2019.
arXiv:1903.06559

[22] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Science Advances, 1 (9), 2015. 10.1126/​sciadv.1500838.
https:/​/​doi.org/​10.1126/​sciadv.1500838

[23] Vicky Choi. Minor-embedding in adiabatic quantum computation: I. the parameter setting problem. Quantum Information Processing, 7 (5): 193-209, 2008. 10.1007/​s11128-008-0082-9.
https:/​/​doi.org/​10.1007/​s11128-008-0082-9

[24] Helmut Ritsch, Peter Domokos, Ferdinand Brennecke, and Tilman Esslinger. Cold atoms in cavity-generated dynamical optical potentials. Reviews of Modern Physics, 85 (2): 553, 2013. 10.1103/​RevModPhys.85.553.
https:/​/​doi.org/​10.1103/​RevModPhys.85.553

[25] Christoph Maschler and Helmut Ritsch. Cold atom dynamics in a quantum optical lattice potential. Physical review letters, 95 (26): 260401, 2005. 10.1103/​PhysRevLett.95.260401.
https:/​/​doi.org/​10.1103/​PhysRevLett.95.260401

[26] Renate Landig, Lorenz Hruby, Nishant Dogra, Manuele Landini, Rafael Mottl, Tobias Donner, and Tilman Esslinger. Quantum phases from competing short-and long-range interactions in an optical lattice. Nature, 532 (7600): 476, 2016. 10.1038/​nature17409.
https:/​/​doi.org/​10.1038/​nature17409

[27] Igor B Mekhov and Helmut Ritsch. Quantum optics with ultracold quantum gases: towards the full quantum regime of the light-matter interaction. Journal of Physics B: Atomic, Molecular and Optical Physics, 45 (10): 102001, 2012. 10.1088/​0953-4075/​45/​10/​102001.
https:/​/​doi.org/​10.1088/​0953-4075/​45/​10/​102001

[28] Santiago F Caballero-Benitez, Gabriel Mazzucchi, and Igor B Mekhov. Quantum simulators based on the global collective light-matter interaction. Physical Review A, 93 (6): 063632, 2016. 10.1103/​PhysRevA.93.063632.
https:/​/​doi.org/​10.1103/​PhysRevA.93.063632

[29] Jordan Bell and Brett Stevens. A survey of known results and research areas for n-queens. Discrete Mathematics, 309 (1): 1-31, 2009. 10.1016/​j.disc.2007.12.043.
https:/​/​doi.org/​10.1016/​j.disc.2007.12.043

[30] Ian P Gent, Christopher Jefferson, and Peter Nightingale. Complexity of n-queens completion. Journal of Artificial Intelligence Research, 59: 815-848, 2017. 10.1613/​jair.5512.
https:/​/​doi.org/​10.1613/​jair.5512

[31] Itay Hen. Realizable quantum adiabatic search. EPL (Europhysics Letters), 118 (3): 30003, 2017. 10.1209/​0295-5075/​118/​30003.
https:/​/​doi.org/​10.1209/​0295-5075/​118/​30003

[32] Itay Hen and Federico M Spedalieri. Quantum annealing for constrained optimization. Physical Review Applied, 5 (3): 034007, 2016. 10.1103/​PhysRevApplied.5.034007.
https:/​/​doi.org/​10.1103/​PhysRevApplied.5.034007

[33] Peter Domokos and Helmut Ritsch. Collective cooling and self-organization of atoms in a cavity. Physical review letters, 89 (25): 253003, 2002. 10.1103/​PhysRevLett.89.253003.
https:/​/​doi.org/​10.1103/​PhysRevLett.89.253003

[34] Adam T Black, Hilton W Chan, and Vladan Vuletić. Observation of collective friction forces due to spatial self-organization of atoms: from rayleigh to bragg scattering. Physical review letters, 91 (20): 203001, 2003. 10.1103/​PhysRevLett.91.203001.
https:/​/​doi.org/​10.1103/​PhysRevLett.91.203001

[35] Varun D Vaidya, Yudan Guo, Ronen M Kroeze, Kyle E Ballantine, Alicia J Kollár, Jonathan Keeling, and Benjamin L Lev. Tunable-range, photon-mediated atomic interactions in multimode cavity qed. Physical Review X, 8 (1): 011002, 2018. 10.1103/​PhysRevX.8.011002.
https:/​/​doi.org/​10.1103/​PhysRevX.8.011002

[36] Subhadeep Gupta, Kevin L Moore, Kater W Murch, and Dan M Stamper-Kurn. Cavity nonlinear optics at low photon numbers from collective atomic motion. Physical review letters, 99 (21): 213601, 2007. 10.1103/​PhysRevLett.99.213601.
https:/​/​doi.org/​10.1103/​PhysRevLett.99.213601

[37] Sarang Gopalakrishnan, Benjamin L Lev, and Paul M Goldbart. Frustration and glassiness in spin models with cavity-mediated interactions. Physical review letters, 107 (27): 277201, 2011. 10.1103/​PhysRevLett.107.277201.
https:/​/​doi.org/​10.1103/​PhysRevLett.107.277201

[38] Sarang Gopalakrishnan, Benjamin L Lev, and Paul M Goldbart. Exploring models of associative memory via cavity quantum electrodynamics. Philosophical Magazine, 92 (1-3): 353-361, 2012. 10.1080/​14786435.2011.637980.
https:/​/​doi.org/​10.1080/​14786435.2011.637980

[39] Sebastian Krämer and Helmut Ritsch. Self-ordering dynamics of ultracold atoms in multicolored cavity fields. Physical Review A, 90 (3): 033833, 2014. 10.1103/​PhysRevA.90.033833.
https:/​/​doi.org/​10.1103/​PhysRevA.90.033833

[40] Valentin Torggler, Sebastian Krämer, and Helmut Ritsch. Quantum annealing with ultracold atoms in a multimode optical resonator. Physical Review A, 95 (3): 032310, 2017. 10.1103/​PhysRevA.95.032310.
https:/​/​doi.org/​10.1103/​PhysRevA.95.032310

[41] Igor B Mekhov and Helmut Ritsch. Quantum nondemolition measurements and state preparation in quantum gases by light detection. Physical review letters, 102 (2): 020403, 2009. 10.1103/​PhysRevLett.102.020403.
https:/​/​doi.org/​10.1103/​PhysRevLett.102.020403

[42] Vicky Choi. Minor-embedding in adiabatic quantum computation: Ii. minor-universal graph design. Quantum Information Processing, 10 (3): 343-353, 2011. 10.1007/​s11128-010-0200-3.
https:/​/​doi.org/​10.1007/​s11128-010-0200-3

[43] Andrea Rocchetto, Simon C Benjamin, and Ying Li. Stabilizers as a design tool for new forms of the lechner-hauke-zoller annealer. Science advances, 2 (10): e1601246, 2016. 10.1126/​sciadv.1601246.
https:/​/​doi.org/​10.1126/​sciadv.1601246

[44] Alexander W Glaetzle, Rick MW van Bijnen, Peter Zoller, and Wolfgang Lechner. A coherent quantum annealer with rydberg atoms. Nature Communications, 8: 15813, 2017. 10.1038/​ncomms15813.
https:/​/​doi.org/​10.1038/​ncomms15813

[45] Walter Vinci and Daniel A Lidar. Scalable effective-temperature reduction for quantum annealers via nested quantum annealing correction. Physical Review A, 97 (2): 022308, 2018. 10.1103/​PhysRevA.97.022308.
https:/​/​doi.org/​10.1103/​PhysRevA.97.022308

[46] Layla Hormozi, Ethan W Brown, Giuseppe Carleo, and Matthias Troyer. Nonstoquastic hamiltonians and quantum annealing of an ising spin glass. Physical Review B, 95 (18): 184416, 2017. 10.1103/​PhysRevB.95.184416.
https:/​/​doi.org/​10.1103/​PhysRevB.95.184416

[47] Tameem Albash. Role of nonstoquastic catalysts in quantum adiabatic optimization. Physical Review A, 99 (4): 042334, 2019. 10.1103/​PhysRevA.99.042334.
https:/​/​doi.org/​10.1103/​PhysRevA.99.042334

[48] Sergei V Isakov, Guglielmo Mazzola, Vadim N Smelyanskiy, Zhang Jiang, Sergio Boixo, Hartmut Neven, and Matthias Troyer. Understanding quantum tunneling through quantum monte carlo simulations. Physical review letters, 117 (18): 180402, 2016. 10.1103/​PhysRevLett.117.180402.
https:/​/​doi.org/​10.1103/​PhysRevLett.117.180402

[49] Joel Klassen and Barbara M. Terhal. Two-local qubit Hamiltonians: when are they stoquastic? Quantum, 3: 139, May 2019. ISSN 2521-327X. 10.22331/​q-2019-05-06-139.
https:/​/​doi.org/​10.22331/​q-2019-05-06-139

[50] Milad Marvian, Daniel A Lidar, and Itay Hen. On the computational complexity of curing non-stoquastic hamiltonians. Nature communications, 10 (1): 1571, 2019. 10.1038/​s41467-019-09501-6.
https:/​/​doi.org/​10.1038/​s41467-019-09501-6

[51] Immanuel Bloch. Ultracold quantum gases in optical lattices. Nature Physics, 1 (1): 23-30, 2005. doi.org/​10.1038/​nphys138.
https:/​/​doi.org/​doi.org/​10.1038/​nphys138

[52] Florian Meinert, Manfred J Mark, Emil Kirilov, Katharina Lauber, Philipp Weinmann, Michael Gröbner, Andrew J Daley, and Hanns-Christoph Nägerl. Observation of many-body dynamics in long-range tunneling after a quantum quench. Science, 344 (6189): 1259-1262, 2014. 10.1126/​science.1248402.
https:/​/​doi.org/​10.1126/​science.1248402

[53] Peter Domokos and Helmut Ritsch. Mechanical effects of light in optical resonators. JOSA B, 20 (5): 1098-1130, 2003. 10.1364/​JOSAB.20.001098.
https:/​/​doi.org/​10.1364/​JOSAB.20.001098

[54] Christoph Maschler, Igor B Mekhov, and Helmut Ritsch. Ultracold atoms in optical lattices generated by quantized light fields. The European Physical Journal D, 46 (3): 545-560, 2008. 10.1140/​epjd/​e2008-00016-4.
https:/​/​doi.org/​10.1140/​epjd/​e2008-00016-4

[55] Dieter Jaksch, Christoph Bruder, Juan Ignacio Cirac, Crispin W Gardiner, and Peter Zoller. Cold bosonic atoms in optical lattices. Physical Review Letters, 81 (15): 3108, 1998. 10.1103/​PhysRevLett.81.3108.
https:/​/​doi.org/​10.1103/​PhysRevLett.81.3108

[56] Walter Kohn. Analytic properties of bloch waves and wannier functions. Physical Review, 115 (4): 809, 1959. 10.1103/​PhysRev.115.809.
https:/​/​doi.org/​10.1103/​PhysRev.115.809

[57] D Nagy, P Domokos, A Vukics, and H Ritsch. Nonlinear quantum dynamics of two bec modes dispersively coupled by an optical cavity. The European Physical Journal D, 55 (3): 659, 2009. 10.1140/​epjd/​e2009-00265-7.
https:/​/​doi.org/​10.1140/​epjd/​e2009-00265-7

[58] Hessam Habibian, André Winter, Simone Paganelli, Heiko Rieger, and Giovanna Morigi. Bose-glass phases of ultracold atoms due to cavity backaction. Physical review letters, 110 (7): 075304, 2013. 10.1103/​PhysRevLett.110.075304.
https:/​/​doi.org/​10.1103/​PhysRevLett.110.075304

[59] Waseem S Bakr, Jonathon I Gillen, Amy Peng, Simon Fölling, and Markus Greiner. A quantum gas microscope for detecting single atoms in a hubbard-regime optical lattice. Nature, 462 (7269): 74, 2009. 10.1038/​nature08482.
https:/​/​doi.org/​10.1038/​nature08482

[60] Jacob F Sherson, Christof Weitenberg, Manuel Endres, Marc Cheneau, Immanuel Bloch, and Stefan Kuhr. Single-atom-resolved fluorescence imaging of an atomic mott insulator. Nature, 467 (7311): 68, 2010. 10.1038/​nature09378.
https:/​/​doi.org/​10.1038/​nature09378

[61] H. Carmichael. An Open Systems Approach to Quantum Optics: Lectures Presented at the Université Libre de Bruxelles, October 28 to November 4, 1991. Number Bd. 18 in An Open Systems Approach to Quantum Optics: Lectures Presented at the Université Libre de Bruxelles, October 28 to November 4, 1991. Springer Berlin Heidelberg, 1993. ISBN 9783540566342.

[62] Matthias Wolke, Julian Klinner, Hans Keßler, and Andreas Hemmerich. Cavity cooling below the recoil limit. Science, 337 (6090): 75-78, 2012. 10.1126/​science.1219166.
https:/​/​doi.org/​10.1126/​science.1219166

[63] Rounak Jha, Debaiudh Das, Avinash Dash, Sandhya Jayaraman, Bikash K Behera, and Prasanta K Panigrahi. A novel quantum n-queens solver algorithm and its simulation and application to satellite communication using ibm quantum experience. arXiv:1806.10221 [quant-ph], 2018.
arXiv:1806.10221

[64] Sebastian Krämer, David Plankensteiner, Laurin Ostermann, and Helmut Ritsch. Quantumoptics.jl: A julia framework for simulating open quantum systems. Computer Physics Communications, pages -, 2018. ISSN 0010-4655. 10.1016/​j.cpc.2018.02.004.
https:/​/​doi.org/​10.1016/​j.cpc.2018.02.004

Cited by

[1] Philipp Hauke, Helmut G. Katzgraber, Wolfgang Lechner, Hidetoshi Nishimori, and William D. Oliver, "Perspectives of quantum annealing: Methods and implementations", arXiv:1903.06559.

[2] Peter Kirton, Mor M. Roses, Jonathan Keeling, and Emanuele G. Dalla Torre, "Introduction to the Dicke model: from equilibrium to nonequilibrium, and vice versa", arXiv:1805.09828.

[3] Emily J. Davis, Gregory Bentsen, Lukas Homeier, Tracy Li, and Monika H. Schleier-Smith, "Photon-Mediated Spin-Exchange Dynamics of Spin-1 Atoms", Physical Review Letters 122 1, 010405 (2019).

[4] François Damanet, Andrew J. Daley, and Jonathan Keeling, "Atom-only descriptions of the driven-dissipative Dicke model", Physical Review A 99 3, 033845 (2019).

[5] Ronen M. Kroeze, Yudan Guo, Varun D. Vaidya, Jonathan Keeling, and Benjamin L. Lev, "Spinor Self-Ordering of a Quantum Gas in a Cavity", Physical Review Letters 121 16, 163601 (2018).

[6] Rounak Jha, Debaiudh Das, Avinash Dash, Sandhya Jayaraman, Bikash K. Behera, and Prasanta K. Panigrahi, "A Novel Quantum N-Queens Solver Algorithm and its Simulation and Application to Satellite Communication Using IBM Quantum Experience", arXiv:1806.10221.

The above citations are from SAO/NASA ADS (last updated 2019-10-20 19:34:26). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2019-10-20 19:34:25).

1 thought on “A Quantum N-Queens Solver

  1. Pingback: Is kwantumrekenen wel zo superieur? Wellicht - Geleerd uitschotGeleerd uitschot