Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach

Jordi R. Weggemans1,2, Alexander Urech2,3, Alexander Rausch4, Robert Spreeuw2,3, Richard Boucherie5, Florian Schreck2,3, Kareljan Schoutens2,6, Jiří Minář2,6, and Florian Speelman2,7

1CWI, Science Park 123, 1098 XG Amsterdam, The Netherlands
2QuSoft, Science Park 123, 1098 XG Amsterdam, The Netherlands
3Van der Waals-Zeeman Institute, Institute of Physics, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands
4Robert Bosch GmbH, Corporate Research, Robert-Bosch-Campus 1, 71272 Renningen, Germany
5Stochastic Operations Research, Department of Applied Mathematics, University of Twente, 7500 AE, Enschede, The Netherlands.
6Institute for Theoretical Physics, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands
7Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, the Netherlands

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


We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits, which constitute a natural platform for such non-binary problems. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering, including Hamiltonian formulation of the algorithm, analysis of its performance, identification of a suitable level structure for ${}^{87}{\rm Sr}$ and specific gate design. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count. For single layer QAOA, we also prove (conjecture) a lower bound of $0.6367$ ($0.6699$) for the approximation ratio on 3-regular graphs. Our numerical studies evaluate the algorithm's performance by considering complete and Erdős-Rényi graphs of up to 7 vertices and clusters. We find that in all cases the QAOA surpasses the Swamy bound $0.7666$ for the approximation ratio for QAOA depths $p \geq 2$. Finally, by analysing the effect of errors when solving complete graphs we find that their inclusion severely limits the algorithm's performance.

► BibTeX data

► References

[1] Atom computing. https:/​/​​.

[2] Coldquanta. https:/​/​​.

[3] Pasqal. https:/​/​​.

[4] Quera. https:/​/​​.

[5] Scipy documentation. https:/​/​

[6] Nir Ailon, Moses Charikar, and Alantha Newman. Aggregating inconsistent information: Ranking and clustering. J. ACM, 55 (5), November 2008. ISSN 0004-5411. 10.1145/​1411509.1411513.

[7] V. Akshay, H. Philathong, M. E. S. Morales, and J. D. Biamonte. Reachability Deficits in Quantum Approximate Optimization. , 124 (9): 090504, March 2020. 10.1103/​PhysRevLett.124.090504.

[8] V. Akshay, D. Rabinovich, E. Campos, and J. Biamonte. Parameter concentrations in quantum approximate optimization. , 104 (1): L010401, July 2021. 10.1103/​PhysRevA.104.L010401.

[9] Victor V. Albert, Jacob P. Covey, and John Preskill. Robust Encoding of a Qubit in a Molecule. Physical Review X, 10 (3): 031050, July 2020. 10.1103/​PhysRevX.10.031050.

[10] Yuri Alexeev, Dave Bacon, Kenneth R. Brown, Robert Calderbank, Lincoln D. Carr, Frederic T. Chong, Brian DeMarco, Dirk Englund, Edward Farhi, Bill Fefferman, Alexey V. Gorshkov, Andrew Houck, Jungsang Kim, Shelby Kimmel, Michael Lange, Seth Lloyd, Mikhail D. Lukin, Dmitri Maslov, Peter Maunz, Christopher Monroe, John Preskill, Martin Roetteler, Martin J. Savage, and Jeff Thompson. Quantum computer systems for scientific discovery. PRX Quantum, 2: 017001, Feb 2021. 10.1103/​PRXQuantum.2.017001.

[11] James M. Auger, Silvia Bergamini, and Dan E. Browne. Blueprint for fault-tolerant quantum computation with rydberg atoms. Phys. Rev. A, 96: 052320, Nov 2017. 10.1103/​PhysRevA.96.052320.

[12] Amin Babazadeh, Manuel Erhard, Feiran Wang, Mehul Malik, Rahman Nouroozi, Mario Krenn, and Anton Zeilinger. High-dimensional single-photon quantum gates: Concepts and experiments. Phys. Rev. Lett., 119: 180510, Nov 2017. 10.1103/​PhysRevLett.119.180510.

[13] Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, and Garnet Kin-Lic Chan. Low-depth quantum simulation of materials. Phys. Rev. X, 8: 011044, Mar 2018. 10.1103/​PhysRevX.8.011044.

[14] Shai Bagon and Meirav Galun. Large Scale Correlation Clustering Optimization. arXiv e-prints, art. arXiv:1112.2903, December 2011. 10.48550/​arXiv.1112.2903.

[15] S Balakrishnan. Various constructions of qudit swap gate. Physics Research International, 2014, 2014. 10.1155/​2014/​479320.

[16] Nikhil Bansal, Avrim Blum, and Shuchi Chawla. Correlation clustering. Mach. Learn., 56 (1-3): 89–113, 2004. 10.1023/​B:MACH.0000033116.57574.95.

[17] Adriano Barenco, Charles H. Bennett, Richard Cleve, David P. DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A. Smolin, and Harald Weinfurter. Elementary gates for quantum computation. Phys. Rev. A, 52: 3457–3467, Nov 1995. 10.1103/​PhysRevA.52.3457.

[18] Daniel Barredo, Sylvain de Léséleuc, Vincent Lienhard, Thierry Lahaye, and Antoine Browaeys. An atom-by-atom assembler of defect-free arbitrary two-dimensional atomic arrays. Science, 354 (6315): 1021–1023, nov 2016. ISSN 0036-8075. 10.1126/​science.aah3778.

[19] Daniel Barredo, Vincent Lienhard, Sylvain de Léséleuc, Thierry Lahaye, and Antoine Browaeys. Synthetic three-dimensional atomic structures assembled atom by atom. , 561 (7721): 79–82, September 2018. 10.1038/​s41586-018-0450-2.

[20] Bela Bauer, Philippe Corboz, Andreas M. Läuchli, Laura Messio, Karlo Penc, Matthias Troyer, and Frédéric Mila. Three-sublattice order in the su(3) heisenberg model on the square and triangular lattice. Phys. Rev. B, 85: 125116, Mar 2012. 10.1103/​PhysRevB.85.125116.

[21] Omar Benjelloun, Hector Garcia-Molina, David Menestrina, Qi Su, Steven Euijong Whang, and Jennifer Widom. Swoosh: a generic approach to entity resolution. The VLDB Journal, 18 (1): 255–276, 2009. 10.1007/​s00778-008-0098-x.

[22] N. Bent, H. Qassim, A. A. Tahir, D. Sych, G. Leuchs, L. L. Sánchez-Soto, E. Karimi, and R. W. Boyd. Experimental realization of quantum tomography of photonic qudits via symmetric informationally complete positive operator-valued measures. Phys. Rev. X, 5: 041006, Oct 2015. 10.1103/​PhysRevX.5.041006.

[23] Martin M. Boyd, Tanya Zelevinsky, Andrew D. Ludlow, Sebastian Blatt, Thomas Zanon-Willette, Seth M. Foreman, and Jun Ye. Nuclear spin effects in optical lattice clocks. Phys. Rev. A, 76: 022510, Aug 2007. 10.1103/​PhysRevA.76.022510.

[24] Fernando G. S. L. Brandao, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven. For Fixed Control Parameters the Quantum Approximate Optimization Algorithm's Objective Function Value Concentrates for Typical Instances. arXiv e-prints, December 2018. 10.48550/​arXiv.1812.04170.

[25] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Hybrid quantum-classical algorithms for approximate graph coloring. arXiv e-prints, November 2020a. 10.48550/​arXiv.2011.13420.

[26] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to Variational Quantum Optimization from Symmetry Protection. , 125 (26): 260505, December 2020b. 10.1103/​PhysRevLett.125.260505.

[27] Antoine Browaeys and Thierry Lahaye. Many-body physics with individually controlled Rydberg atoms. Nature Physics, 16 (2): 132–142, January 2020. 10.1038/​s41567-019-0733-z.

[28] Andreas Bärtschi and Stephan Eidenbenz. Grover mixers for qaoa: Shifting complexity from mixer design to state preparation. In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 72–82, 2020. 10.1109/​QCE49297.2020.00020.

[29] Stéphane Caron. lpsolvers. https:/​/​​project/​lpsolvers/​, 2007.

[30] Moses Charikar, Venkatesan Guruswami, and Anthony Wirth. Clustering with qualitative information. J. Comput. Syst. Sci., 71: 360–383, 10 2005. 10.1016/​j.jcss.2004.10.012.

[31] Pochung Chen, Zhi-Long Xue, I. P. McCulloch, Ming-Chiang Chung, Chao-Chun Huang, and S. K. Yip. Quantum Critical Spin-2 Chain with Emergent SU(3) Symmetry. , 114 (14): 145301, April 2015. 10.1103/​PhysRevLett.114.145301.

[32] Jahan Claes and Wim van Dam. Instance Independence of Single Layer Quantum Approximate Optimization Algorithm on Mixed-Spin Models at Infinite Size. Quantum, 5: 542, September 2021. ISSN 2521-327X. 10.22331/​q-2021-09-15-542.

[33] Jeremy Cook, Stephan Eidenbenz, and Andreas Bartschi. The quantum alternating operator ansatz on maximum k-vertex cover. pages 83–92, 10 2020. 10.1109/​QCE49297.2020.00021.

[34] Philippe Corboz, Andreas M. Läuchli, Karlo Penc, Matthias Troyer, and Frédéric Mila. Simultaneous Dimerization and SU(4) Symmetry Breaking of 4-Color Fermions on the Square Lattice. , 107 (21): 215301, November 2011. 10.1103/​PhysRevLett.107.215301.

[35] Philippe Corboz, Karlo Penc, Frédéric Mila, and Andreas M. Läuchli. Simplex solids in SU(N) Heisenberg models on the kagome and checkerboard lattices. , 86 (4): 041106, July 2012. 10.1103/​PhysRevB.86.041106.

[36] Philippe Corboz, Miklós Lajkó, Karlo Penc, Frédéric Mila, and Andreas M. Läuchli. Competing states in the SU(3) Heisenberg model on the honeycomb lattice: Plaquette valence-bond crystal versus dimerized color-ordered state. , 87 (19): 195113, May 2013. 10.1103/​PhysRevB.87.195113.

[37] Jacob P. Covey, Ivaylo S. Madjarov, Alexandre Cooper, and Manuel Endres. 2000-times repeated imaging of strontium atoms in clock-magic tweezer arrays. Phys. Rev. Lett., 122: 173201, May 2019. 10.1103/​PhysRevLett.122.173201.

[38] Constantin Dalyac, Loïc Henriet, Emmanuel Jeandel, Wolfgang Lechner, Simon Perdrix, Marc Porcheron, and Margarita Veshchezerova. Qualifying quantum approaches for hard industrial optimization problems. a case study in the field of smart-charging of electric vehicles. EPJ Quantum Technology, 8 (12), May 2021. 10.1140/​epjqt/​s40507-021-00100-3.

[39] Jonathan D'Emidio, Matthew S. Block, and Ribhu K. Kaul. Rényi entanglement entropy of critical SU (N ) spin chains. , 92 (5): 054411, August 2015. 10.1103/​PhysRevB.92.054411.

[40] B DeSalvo, Mi Yan, P Mickelson, Y. Escobar, and T Killian. Degenerate fermi gas of sr-87. Physical Review Letters, 105: 030402, 07 2010. 10.1103/​PhysRevLett.105.030402.

[41] Ivan H. Deutsch and Poul S. Jessen. Quantum-state control in optical lattices. Phys. Rev. A, 57: 1972–1986, Mar 1998. 10.1103/​PhysRevA.57.1972.

[42] Cirq Developers. Cirq, May 2021. See full list of authors on Github: https:/​/​github .com/​quantumlib/​Cirq/​graphs/​contributors.

[43] Josep Díaz and Marcin Jakub Kaminski. Max-cut and max-bisection are np-hard on unit disk graphs. Theor. Comput. Sci., 377: 271–276, 2007. 10.1016/​j.tcs.2007.02.013.

[44] Shruti Dogra, Arvind, and Kavita Dorai. Determining the parity of a permutation using an experimental NMR qutrit. Physics Letters A, 378 (46): 3452–3456, October 2014. 10.1016/​j.physleta.2014.10.003.

[45] Jérôme Dufour, Pierre Nataf, and Frédéric Mila. Variational Monte Carlo investigation of SU (N ) Heisenberg chains. , 91 (17): 174427, May 2015. 10.1103/​PhysRevB.91.174427.

[46] Micha Elsner and Warren Schudy. Bounding and comparing methods for correlation clustering beyond ilp. In Proceedings of the Workshop on Integer Linear Programming for Natural Langauge Processing, ILP '09, page 19–27, USA, 2009. Association for Computational Linguistics. ISBN 9781932432350. 10.3115/​1611638.1611641.

[47] Dotan Emanuel and Amos Fiat. Correlation clustering – minimizing disagreements on arbitrary weighted graphs. In Giuseppe Di Battista and Uri Zwick, editors, Algorithms - ESA 2003, pages 208–220, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. ISBN 978-3-540-39658-1. 10.1007/​978-3-540-39658-1_21.

[48] Manuel Endres, Hannes Bernien, Alexander Keesling, Harry Levine, Eric R. Anschuetz, Alexandre Krajenbrink, Crystal Senko, Vladan Vuletic, Markus Greiner, and Mikhail D. Lukin. Atom-by-atom assembly of defect-free one-dimensional cold atom arrays. Science, 354 (6315): 1024–1027, November 2016. 10.1126/​science.aah3752.

[49] Edward Farhi and Aram W Harrow. Quantum Supremacy through the Quantum Approximate Optimization Algorithm. arXiv e-prints, February 2016. 10.48550/​arXiv.1602.07674.

[50] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm. arXiv e-prints, November 2014a. 10.48550/​arXiv.1411.4028.

[51] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem. arXiv e-prints, December 2014b. 10.48550/​arXiv.1412.6062.

[52] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Leo Zhou. The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size. arXiv e-prints, October 2019. 10.48550/​arXiv.1910.08187.

[53] Edward Farhi, David Gamarnik, and Sam Gutmann. The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: A Typical Case. arXiv e-prints, April 2020. 10.48550/​arXiv.2004.09002.

[54] Franz G Fuchs, Herman Øie Kolden, Niels Henrik Aase, and Giorgio Sartor. Efficient encoding of the weighted max k-cut on a quantum computer using qaoa. SN Computer Science, 2 (2): 1–14, 2021. 10.1007/​s42979-020-00437-z.

[55] Takeshi Fukuhara, Yosuke Takasu, Mitsutaka Kumakura, and Yoshiro Takahashi. Degenerate fermi gases of ytterbium. Phys. Rev. Lett., 98: 030401, Jan 2007. 10.1103/​PhysRevLett.98.030401.

[56] Thomas F. Gallagher. Rydberg Atoms. Cambridge Monographs on Atomic, Molecular and Chemical Physics. Cambridge University Press, 1994. 10.1017/​CBO9780511524530.

[57] Juan Carlos Garcia-Escartin and Pedro Chamorro-Posada. A swap gate for qudits. Quantum information processing, 12 (12): 3625–3631, 2013. 10.1007/​s11128-013-0621-x.

[58] Z. Gedik, I. A. Silva, B. Çakmak, G. Karpat, E. L. G. Vidoto, D. O. Soares-Pinto, E. R. Deazevedo, and F. F. Fanchini. Computational speed-up with a single qudit. Scientific Reports, 5: 14671, October 2015. 10.1038/​srep14671.

[59] Aristides Gionis, Heikki Mannila, and Panayiotis Tsaparas. Clustering aggregation. ACM Trans. Knowl. Discov. Data, 1 (1): 4–es, March 2007. ISSN 1556-4681. 10.1145/​1217299.1217303.

[60] Ioannis Giotis and Venkatesan Guruswami. Correlation clustering with a fixed number of clusters. In In Proc. 17th ACM-SIAM SODA, pages 1167–1176. ACM Press, 2006. 10.4086/​toc.2006.v002a013.

[61] Andrey Goder and Vladimir Filkov. Consensus clustering algorithms: Comparison and refinement. In Proceedings of the Meeting on Algorithm Engineering & Expermiments, page 109–117, USA, 2008. Society for Industrial and Applied Mathematics. 10.1137/​1.9781611972887.11.

[62] G. G. Guerreschi and A. Y. Matsuura. QAOA for Max-Cut requires hundreds of qubits for quantum speed-up. Scientific Reports, 9: 6903, May 2019. 10.1038/​s41598-019-43176-9.

[63] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli, and Rupak Biswas. From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz. arXiv e-prints, September 2017. 10.48550/​arXiv.1709.03489.

[64] Matthew P Harrigan, Kevin J Sung, Matthew Neeley, Kevin J Satzinger, Frank Arute, Kunal Arya, Juan Atalaya, Joseph C Bardin, Rami Barends, Sergio Boixo, et al. Quantum approximate optimization of non-planar graph problems on a planar superconducting processor. Nature Physics, 17 (3): 332–336, 2021. 10.1038/​s41567-020-01105-y.

[65] M. B. Hastings. Classical and Quantum Bounded Depth Approximation Algorithms. arXiv e-prints, May 2019. 10.48550/​arXiv.1905.07047.

[66] Loïc Henriet. Robustness to spontaneous emission of a variational quantum algorithm. Phys. Rev. A, 101: 012335, Jan 2020. 10.1103/​PhysRevA.101.012335.

[67] Loïc Henriet, Lucas Beguin, Adrien Signoles, Thierry Lahaye, Antoine Browaeys, Georges-Olivier Reymond, and Christophe Jurczak. Quantum computing with neutral atoms. Quantum, 4: 327, 2020. 10.22331/​q-2020-09-21-327.

[68] Riaz Hussain, Giuseppe Allodi, Alessandro Chiesa, Elena Garlatti, Dmitri Mitcov, Andreas Konstantatos, Kasper Pedersen, Roberto De Renzi, Stergios Piligkos, and Stefano Carretta. Coherent manipulation of a molecular ln-based nuclear qudit coupled to an electron qubit. Journal of the American Chemical Society, 140, 07 2018. 10.1021/​jacs.8b05934.

[69] Victor Il'ev, Svetlana Il'eva, and Alexander Kononov. Short survey on graph correlation clustering with minimization criteria. In Yury Kochetov, Michael Khachay, Vladimir Beresnev, Evgeni Nurminski, and Panos Pardalos, editors, Discrete Optimization and Operations Research, pages 25–36, Cham, 2016. Springer International Publishing. ISBN 978-3-319-44914-2. 10.1007/​978-3-319-44914-2_3.

[70] Poolad Imany, Jose A. Jaramillo-Villegas, Ogaga D. Odele, Kyunghun Han, Daniel E. Leaird, Joseph M. Lukens, Pavel Lougovski, Minghao Qi, and Andrew M. Weiner. 50-ghz-spaced comb of high-dimensional frequency-bin entangled photons from an on-chip silicon nitride microresonator. Optics Express, 26 (2), 1 2018. 10.1364/​OE.26.001825.

[71] Eldar Insafutdinov, Leonid Pishchulin, Bjoern Andres, Mykhaylo Andriluka, and Bernt Schiele. Deepercut: A deeper, stronger, and faster multi-person pose estimation model. In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision – ECCV 2016, pages 34–50, Cham, 2016. Springer International Publishing. ISBN 978-3-319-46466-4. 10.1007/​978-3-319-46466-4_3.

[72] Nurul T. Islam, Charles Ci Wen Lim, Clinton Cahall, Jungsang Kim, and Daniel J. Gauthier. Provably secure and high-rate quantum key distribution with time-bin qudits. Science Advances, 3 (11): e1701491, November 2017. 10.1126/​sciadv.1701491.

[73] Toshinari Itoko, Rudy Raymond, Takashi Imamichi, and Atsushi Matsuo. Optimization of quantum circuit mapping using gate transformation and commutation. Integration, 70: 43–50, 2020. ISSN 0167-9260. https:/​/​​10.1016/​j.vlsi.2019.10.004.

[74] Zhang Jiang, Eleanor G. Rieffel, and Zhihui Wang. Near-optimal quantum circuit for grover's unstructured search using a transverse field. Phys. Rev. A, 95: 062317, Jun 2017. 10.1103/​PhysRevA.95.062317.

[75] Hong-Wei Jiao, Feng-Hui Wang, and Yong-Qiang Chen. An effective branch and bound algorithm for minimax linear fractional programming. Journal of Applied Mathematics, 2014: 1–8, 2014. 10.1155/​2014/​160262.

[76] E. O. Kiktenko, A. S. Nikolaeva, Peng Xu, G. V. Shlyapnikov, and A. K. Fedorov. Scalable quantum computing with qudits on a graph. Phys. Rev. A, 101: 022304, Feb 2020. 10.1103/​PhysRevA.101.022304.

[77] Francisco H. Kim, Karlo Penc, Pierre Nataf, and Frédéric Mila. Linear flavor-wave theory for fully antisymmetric SU(N ) irreducible representations. , 96 (20): 205142, November 2017. 10.1103/​PhysRevB.96.205142.

[78] Ian D. Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, and Ryan Babbush. Quantum simulation of electronic structure with linear depth and connectivity. Phys. Rev. Lett., 120: 110501, Mar 2018. 10.1103/​PhysRevLett.120.110501.

[79] Philip N. Klein, Claire Mathieu, and Hang Zhou. Correlation clustering and two-edge-connected augmentation for planar graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, pages 554–567, 2015. 10.4230/​LIPIcs.STACS.2015.554.

[80] Michael Kues, Christian Reimer, Piotr Roztocki, Luis Romero Cortés, Stefania Sciara, Benjamin Wetzel, Yanbing Zhang, Alfonso Cino, Sai T. Chu, Brent E. Little, David J. Moss, Lucia Caspani, José Azaña, and Roberto Morandotti. On-chip generation of high-dimensional entangled quantum states and their coherent control. , 546 (7660): 622–626, June 2017. 10.1038/​nature22986.

[81] Wim Lavrijsen, Ana Tudor, Juliane Müller, Costin Iancu, and Wibe de Jong. Classical Optimizers for Noisy Intermediate-Scale Quantum Devices. arXiv e-prints, art. arXiv:2004.03004, April 2020. 10.48550/​arXiv.2004.03004.

[82] F. M. Leupold, M. Malinowski, C. Zhang, V. Negnevitsky, A. Cabello, J. Alonso, and J. P. Home. Sustained state-independent quantum contextual correlations from a single ion. Phys. Rev. Lett., 120: 180401, May 2018. 10.1103/​PhysRevLett.120.180401.

[83] Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Tout T. Wang, Sepehr Ebadi, Hannes Bernien, Markus Greiner, Vladan Vuletić, Hannes Pichler, and Mikhail D. Lukin. Parallel implementation of high-fidelity multiqubit gates with neutral atoms. Phys. Rev. Lett., 123: 170503, Oct 2019. 10.1103/​PhysRevLett.123.170503.

[84] Norbert M Linke, Dmitri Maslov, Martin Roetteler, Shantanu Debnath, Caroline Figgatt, Kevin A Landsman, Kenneth Wright, and Christopher Monroe. Experimental comparison of two quantum computing architectures. Proceedings of the National Academy of Sciences, 114 (13): 3305–3310, 2017. 10.1073/​pnas.1618020114.

[85] Yang Liu, Gui Lu Long, and Yang Sun. Analytic Constructions of General n-Qubit Controlled Gates. arXiv e-prints, August 2007. 10.48550/​arXiv.0708.3274.

[86] Seth Lloyd. Quantum approximate optimization is computationally universal. arXiv e-prints, December 2018. 10.48550/​arXiv.1812.11075.

[87] Hsuan-Hao Lu, Joseph M. Lukens, Nicholas A. Peters, Ogaga D. Odele, Daniel E. Leaird, Andrew M. Weiner, and Pavel Lougovski. Electro-optic frequency beam splitters and tritters for high-fidelity photonic quantum information processing. Phys. Rev. Lett., 120: 030502, Jan 2018. 10.1103/​PhysRevLett.120.030502.

[88] Ivaylo S. Madjarov, Jacob P. Covey, Adam L. Shaw, Joonhee Choi, Anant Kale, Alexandre Cooper, Hannes Pichler, Vladimir Schkolnik, Jason R. Williams, and Manuel Endres. High-fidelity entanglement and detection of alkaline-earth Rydberg atoms. Nature Physics, 16 (8): 857–861, May 2020. 10.1038/​s41567-020-0903-z.

[89] Ivaylo Sashkov Madjarov. Entangling, Controlling, and Detecting Individual Strontium Atoms in Optical Tweezer Arrays. PhD thesis, California Institute of Technology, 2021.

[90] Kunal Marwaha. Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs. Quantum, 5: 437, April 2021. ISSN 2521-327X. 10.22331/​q-2021-04-20-437.

[91] Matija Medvidović and Giuseppe Carleo. Classical variational simulation of the Quantum Approximate Optimization Algorithm. npj Quantum Information, 7: 101, January 2021. 10.1038/​s41534-021-00440-z.

[92] M. E. S. Morales, J. D. Biamonte, and Z. Zimborás. On the universality of the quantum approximate optimization algorithm. Quantum Information Processing, 19 (9): 291, August 2020. 10.1007/​s11128-020-02748-9.

[93] M. Morgado and S. Whitlock. Quantum simulation and computing with Rydberg-interacting qubits. AVS Quantum Science, 3 (2): 023501, June 2021. 10.1116/​5.0036562.

[94] Fabrizio Moro, Alistair J. Fielding, Lyudmila Turyanska, and Amalia Patanè. Realization of universal quantum gates with spin-qudits in colloidal quantum dots. Advanced Quantum Technologies, 2 (10): 1900017, 2019. https:/​/​​10.1002/​qute.201900017.

[95] Pierre Nataf and Frédéric Mila. Exact Diagonalization of Heisenberg SU(N) Models. , 113 (12): 127204, September 2014. 10.1103/​PhysRevLett.113.127204.

[96] Pierre Nataf and Frédéric Mila. Exact diagonalization of Heisenberg SU (N ) chains in the fully symmetric and antisymmetric representations. , 93 (15): 155134, April 2016. 10.1103/​PhysRevB.93.155134.

[97] Pierre Nataf and Frédéric Mila. Density matrix renormalization group simulations of SU(N ) Heisenberg chains using standard Young tableaus: Fundamental representation and comparison with a finite-size Bethe ansatz. , 97 (13): 134420, April 2018. 10.1103/​PhysRevB.97.134420.

[98] Pierre Nataf, Miklós Lajkó, Philippe Corboz, Andreas M. Läuchli, Karlo Penc, and Frédéric Mila. Plaquette order in the SU(6) Heisenberg model on the honeycomb lattice. , 93 (20): 201113, May 2016. 10.1103/​PhysRevB.93.201113.

[99] Matthew Neeley, Markus Ansmann, Radoslaw C. Bialczak, Max Hofheinz, Erik Lucero, Aaron D. O'Connell, Daniel Sank, Haohua Wang, James Wenner, Andrew N. Cleland, Michael R. Geller, and John M. Martinis. Emulation of a Quantum Spin with a Superconducting Phase Qudit. Science, 325 (5941): 722, August 2009. 10.1126/​science.1173440.

[100] Vincent Ng and Claire Cardie. Improving machine learning approaches to coreference resolution. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, pages 104–111, Philadelphia, Pennsylvania, USA, July 2002. Association for Computational Linguistics. 10.3115/​1073083.1073102.

[101] Dianne P. O'Leary, Gavin K. Brennen, and Stephen S. Bullock. Parallelism for quantum computation with qudits. Phys. Rev. A, 74: 032334, Sep 2006. 10.1103/​PhysRevA.74.032334.

[102] Oleksiy Onishchenko, Sergey Pyatchenkov, Alexander Urech, Chun-Chia Chen, Shayne Bennetts, Georgios A. Siviloglou, and Florian Schreck. Frequency of the ultranarrow $^{1}\mathrm{S}_{0}{-}^{3}\mathrm{P}_{2}$ transition in $^{87}\mathrm{Sr}$. Phys. Rev. A, 99: 052503, May 2019. 10.1103/​PhysRevA.99.052503.

[103] Hannes Pichler, Sheng-Tao Wang, Leo Zhou, Soonwon Choi, and Mikhail D. Lukin. Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays. arXiv e-prints, art. arXiv:1808.10816, August 2018a. 10.48550/​arXiv.1808.10816.

[104] Hannes Pichler, Sheng-Tao Wang, Leo Zhou, Soonwon Choi, and Mikhail D. Lukin. Computational complexity of the Rydberg blockade in two dimensions. arXiv e-prints, art. arXiv:1809.04954, September 2018b. 10.48550/​arXiv.1809.04954.

[105] Sergey G. Porsev and Andrei Derevianko. Hyperfine quenching of the metastable $^{3}\mathrm{P}_{0,2}$ states in divalent atoms. Phys. Rev. A, 69: 042506, Apr 2004. 10.1103/​PhysRevA.69.042506.

[106] J. Randall, S. Weidt, E. D. Standing, K. Lake, S. C. Webster, D. F. Murgia, T. Navickas, K. Roth, and W. K. Hensinger. Efficient preparation and detection of microwave dressed-state qubits and qutrits with trapped ions. , 91 (1): 012322, January 2015. 10.1103/​PhysRevA.91.012322.

[107] Christian Reimer, Stefania Sciara, Piotr Roztocki, Mehedi Islam, Luis Romero Cortés, Yanbing Zhang, Bennet Fischer, Sébastien Loranger, Raman Kashyap, Alfonso Cino, et al. High-dimensional one-way quantum processing implemented on d-level cluster states. Nature Physics, 15 (2): 148–153, 2019. 10.1038/​s41567-018-0347-x.

[108] Christian Romen and Andreas M. Läuchli. Structure of spin correlations in high-temperature SU (N ) quantum magnets. Physical Review Research, 2 (4): 043009, October 2020. 10.1103/​PhysRevResearch.2.043009.

[109] M. Saffman. Quantum computing with atomic qubits and Rydberg interactions: progress and challenges. Journal of Physics B Atomic Molecular Physics, 49 (20): 202001, October 2016. 10.1088/​0953-4075/​49/​20/​202001.

[110] M. Saffman and K. Mølmer. Scaling the neutral-atom rydberg gate quantum computer by collective encoding in holmium atoms. Phys. Rev. A, 78: 012336, Jul 2008. 10.1103/​PhysRevA.78.012336.

[111] M. Saffman and T. G. Walker. Analysis of a quantum logic device based on dipole-dipole interactions of optically trapped rydberg atoms. Phys. Rev. A, 72: 022347, Aug 2005. 10.1103/​PhysRevA.72.022347.

[112] M. Saffman, T. G. Walker, and K. Mølmer. Quantum information with rydberg atoms. Rev. Mod. Phys., 82: 2313–2363, Aug 2010. 10.1103/​RevModPhys.82.2313.

[113] M. Safronova. private communication.

[114] S. Saskin, J. T. Wilson, B. Grinkemeyer, and J. D. Thompson. Narrow-line cooling and imaging of ytterbium atoms in an optical tweezer array. Phys. Rev. Lett., 122: 143002, Apr 2019. 10.1103/​PhysRevLett.122.143002.

[115] Rahul Sawant, Jacob A. Blackmore, Philip D. Gregory, Jordi Mur-Petit, Dieter Jaksch, Jesús Aldegunde, Jeremy M. Hutson, M. R. Tarbutt, and Simon L. Cornish. Ultracold polar molecules as qudits. New Journal of Physics, 22 (1): 013027, January 2020. 10.1088/​1367-2630/​ab60f4.

[116] Pascal Scholl, Michael Schuler, Hannah J. Williams, Alexander A. Eberharter, Daniel Barredo, Kai-Niklas Schymik, Vincent Lienhard, Louis-Paul Henry, Thomas C. Lang, Thierry Lahaye, Andreas M. Läuchli, and Antoine Browaeys. Quantum simulation of 2d antiferromagnets with hundreds of rydberg atoms. Nature, 595 (7866): 233–238, Jul 2021. ISSN 1476-4687. 10.1038/​s41586-021-03585-1.

[117] Kai-Niklas Schymik, Vincent Lienhard, Daniel Barredo, Pascal Scholl, Hannah Williams, Antoine Browaeys, and Thierry Lahaye. Enhanced atom-by-atom assembly of arbitrary tweezer arrays. Phys. Rev. A, 102: 063107, Dec 2020. 10.1103/​PhysRevA.102.063107.

[118] Marlan O Scully and M Suhail Zubairy. Quantum optics, 1999. 10.1017/​CBO9780511813993.

[119] G. Semeghini, H. Levine, A. Keesling, S. Ebadi, T. T. Wang, D. Bluvstein, R. Verresen, H. Pichler, M. Kalinowski, R. Samajdar, A. Omran, S. Sachdev, A. Vishwanath, M. Greiner, V. Vuletić, and M. D. Lukin. Probing topological spin liquids on a programmable quantum simulator. Science, 374 (6572): 1242–1247, 2021. 10.1126/​science.abi8794.

[120] C. Senko, P. Richerme, J. Smith, A. Lee, I. Cohen, A. Retzker, and C. Monroe. Realization of a Quantum Integer-Spin Chain with Controllable Interactions. Physical Review X, 5 (2): 021026, April 2015. 10.1103/​PhysRevX.5.021026.

[121] Ruslan Shaydulin, Ilya Safro, and Jeffrey Larson. Multistart methods for quantum approximate optimization. 2019 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–8, 2019. 10.1109/​HPEC.2019.8916288.

[122] Tycho Sleator and Harald Weinfurter. Realizable universal quantum logic gates. Phys. Rev. Lett., 74: 4087–4090, May 1995. 10.1103/​PhysRevLett.74.4087.

[123] V. A. Soltamov, C. Kasper, A. V. Poshakinskiy, A. N. Anisimov, E. N. Mokhov, A. Sperlich, S. A. Tarasenko, P. G. Baranov, G. V. Astakhov, and V. Dyakonov. Excitation and coherent control of spin qudit modes in silicon carbide at room temperature. Nature Communications, 10: 1678, April 2019. 10.1038/​s41467-019-09429-x.

[124] Hao Song and Michael Hermele. Mott insulators of ultracold fermionic alkaline earth atoms in three dimensions. , 87 (14): 144423, April 2013. 10.1103/​PhysRevB.87.144423.

[125] Wee Meng Soon, Hwee Tou Ng, and Daniel Chung Yong Lim. A machine learning approach to coreference resolution of noun phrases. Computational Linguistics, 27 (4): 521–544, 2001. 10.1162/​089120101753342653.

[126] Adam Steck. Quantum and atom optics. URL https:/​/​​ dsteck/​teaching/​quantum-optics/​quantum-optics-notes.pdf.

[127] Simon Stellmer, Rudolf Grimm, and Florian Schreck. Production of quantum-degenerate strontium gases. Phys. Rev. A, 87: 013611, Jan 2013. 10.1103/​PhysRevA.87.013611.

[128] Simon Stellmer, Florian Schreck, and Thomas C. Killian. Degenerate Quantum Gases of Strontium. In Kirk W. Madison and et al., editors, Annual Review of Cold Atoms and Molecules - Volume 2, volume 2, pages 1–80. 2014. 10.1142/​9100.

[129] Daniel Stilck França and Raul García-Patrón. Limitations of optimization algorithms on noisy quantum devices. Nature Physics, 17 (11): 1221–1227, October 2021. 10.1038/​s41567-021-01356-3.

[130] Michael Streif and Martin Leib. Training the Quantum Approximate Optimization Algorithm Without Access to a Quantum Processing Unit. Quantum Science and Technology, 5 (3), July 2020. 10.1088/​2058-9565/​ab8c2b.

[131] Ashok Muthukrishnan CR Stroud. Quantum fast fourier transform using multilevel atoms. journal of modern optics, 49 (13): 2115–2127, 2002. 10.1080/​09500340210123947.

[132] S. Sugawa, Y. Takasu, K. Enomoto, and Y. Takahashi. Ultracold Ytterbium:. Generation, Many-Body Physics, and Molecules. In Annual Review of Cold Atoms and Molecules, volume 1, pages 3–51. 2013. 10.1142/​8632.

[133] Elisha Svetitsky, Haim Suchowski, Roy Resh, Yoni Shalibo, John M. Martinis, and Nadav Katz. Hidden two-qubit dynamics of a four-level Josephson circuit. Nature Communications, 5: 5617, November 2014. 10.1038/​ncomms6617.

[134] Chaitanya Swamy. Correlation clustering: Maximizing agreements via semidefinite programming. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, volume 15, pages 526–527, 01 2004. 10.5555/​982792.

[135] Shintaro Taie, Yosuke Takasu, Seiji Sugawa, Rekishu Yamazaki, Takuya Tsujimoto, Ryo Murakami, and Yoshiro Takahashi. Realization of a $\mathrm{SU}(2)\times{}\mathrm{SU}(6)$ system of fermions in a cold atomic gas. Phys. Rev. Lett., 105: 190401, Nov 2010. 10.1103/​PhysRevLett.105.190401.

[136] Jinsong Tan. A note on the inapproximability of correlation clustering. Information Processing Letters, 108 (5): 331–335, 2008. ISSN 0020-0190. https:/​/​​10.1016/​j.ipl.2008.06.004.

[137] Xinsheng Tan, Dan-Wei Zhang, Wen Zheng, Xiaopei Yang, Shuqing Song, Zhikun Han, Yuqian Dong, Zhimin Wang, Dong Lan, Hui Yan, Shi-Liang Zhu, and Yang Yu. Experimental Observation of Tensor Monopoles with a Superconducting Qudit. , 126 (1): 017702, January 2021. 10.1103/​PhysRevLett.126.017702.

[138] A. Urech. Ph.D. Thesis, University of Amsterdam, In preparation.

[139] A. Urech, I. Knotterus, R. Spreeuw, and F. Schreck. In preparation.

[140] N. Šibalić, J. D. Pritchard, C. S. Adams, and K. J. Weatherill. ARC: An open-source library for calculating properties of alkali Rydberg atoms. Computer Physics Communications, 220: 319–331, November 2017. 10.1016/​j.cpc.2017.06.015.

[141] Nikola Šibalić, Jonathan D. Pritchard, Charles S. Adams, and Kevin J. Weatherill. Arc package. https:/​/​​en/​latest/​.

[142] Jianwei Wang, Stefano Paesani, Yunhong Ding, Raffaele Santagati, Paul Skrzypczyk, Alexia Salavrakos, Jordi Tura, Remigiusz Augusiak, Laura Mančinska, Davide Bacco, Damien Bonneau, Joshua W. Silverstone, Qihuang Gong, Antonio Acín, Karsten Rottwitt, Leif K. Oxenløwe, Jeremy L. O’Brien, Anthony Laing, and Mark G. Thompson. Multidimensional quantum entanglement with large-scale integrated optics. Science, 360 (6386): 285–291, April 2018a. 10.1126/​science.aar7053.

[143] Yibo Wang, Sayali Shevate, Tobias Martin Wintermantel, Manuel Morgado, Graham Lochead, and Shannon Whitlock. Preparation of hundreds of microscopic atomic ensembles in optical tweezer arrays. npj Quantum Information, 6: 54, January 2020a. 10.1038/​s41534-020-0285-1.

[144] Yuchen Wang, Zixuan Hu, Barry C. Sanders, and Sabre Kais. Qudits and high-dimensional quantum computing. Frontiers in Physics, 8: 479, November 2020b. 10.3389/​fphy.2020.589504.

[145] Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G. Rieffel. Quantum approximate optimization algorithm for MaxCut: A fermionic view. , 97 (2): 022304, February 2018b. 10.1103/​PhysRevA.97.022304.

[146] Matteo M. Wauters, Glen Bigan Mbeng, and Giuseppe E. Santoro. Polynomial scaling of QAOA for ground-state preparation of the fully-connected p-spin ferromagnet. arXiv e-prints, March 2020. 10.48550/​arXiv.2003.07419.

[147] J.R. Weggemans. Solving correlation clustering with the quantum approximate optimisation algorithm. Master's thesis, University of Twente, The Netherlands, December 2020. available at http:/​/​​85484/​.

[148] A. Weichselbaum, S. Capponi, P. Lecheminant, A. M. Tsvelik, and A. M. Läuchli. Unified phase diagram of antiferromagnetic SU(N ) spin ladders. , 98 (8): 085104, August 2018. 10.1103/​PhysRevB.98.085104.

[149] F. Y. Wu. The Potts model. Reviews of Modern Physics, 54 (1): 235–268, January 1982. 10.1103/​RevModPhys.54.235.

[150] Jonathan Wurtz and Peter Love. MaxCut quantum approximate optimization algorithm performance guarantees for $p>1$. , 103 (4): 042612, April 2021. 10.1103/​PhysRevA.103.042612.

[151] Cheng Xue, Zhao-Yun Chen, Yu-Chun Wu, and Guo-Ping Guo. Effects of Quantum Noise on Quantum Approximate Optimization Algorithm. arXiv e-prints, September 2019. 10.48550/​arXiv.1909.02196.

[152] Jun-ichi Yoshikawa, Marcel Bergmann, Peter van Loock, Maria Fuwa, Masanori Okada, Kan Takase, Takeshi Toyama, Kenzo Makino, Shuntaro Takeda, and Akira Furusawa. Heralded creation of photonic qudits from parametric down-conversion using linear optics. Phys. Rev. A, 97: 053814, May 2018. 10.1103/​PhysRevA.97.053814.

[153] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D. Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. Phys. Rev. X, 10: 021067, Jun 2020. 10.1103/​PhysRevX.10.021067.

[154] Linghua Zhu, Ho Lun Tang, George S. Barron, F. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, and Sophia E. Economou. An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer. arXiv e-prints, May 2020. 10.48550/​arXiv.2005.10258.

Cited by

[1] Yannick Deller, Sebastian Schmitt, Maciej Lewenstein, Steve Lenk, Marika Federer, Fred Jendrzejewski, Philipp Hauke, and Valentin Kasper, "Quantum approximate optimization algorithm for qudit systems with long-range interactions", arXiv:2204.00340.

[2] Alexander Urech, Ivo H. A. Knottnerus, Robert J. C. Spreeuw, and Florian Schreck, "Narrow-line imaging of single strontium atoms in shallow optical tweezers", arXiv:2202.05727.

[3] Robert de Keijzer, Oliver Tse, and Servaas Kokkelmans, "Pulse based Variational Quantum Optimal Control for hybrid quantum computing", arXiv:2202.08908.

[4] Aikaterini Gratsea, Valentin Kasper, and Maciej Lewenstein, "Storage properties of a quantum perceptron", arXiv:2111.08414.

[5] Sepehr Assadi and Chen Wang, "Sublinear Time and Space Algorithms for Correlation Clustering via Sparse-Dense Decompositions", arXiv:2109.14528.

[6] Libor Caha, Alexander Kliesch, and Robert Koenig, "Twisted hybrid algorithms for combinatorial optimization", arXiv:2203.00717.

The above citations are from SAO/NASA ADS (last updated successfully 2022-05-28 18:57:42). 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 2022-05-28 18:57:40).