Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT)

Medina Ramos RA, Serbyn M. 2021. Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT). Physical Review A. 104(6), 062423.


Journal Article | Published | English
Department
Abstract
Classical models with complex energy landscapes represent a perspective avenue for the near-term application of quantum simulators. Until now, many theoretical works studied the performance of quantum algorithms for models with a unique ground state. However, when the classical problem is in a so-called clustering phase, the ground state manifold is highly degenerate. As an example, we consider a 3-XORSAT model defined on simple hypergraphs. The degeneracy of classical ground state manifold translates into the emergence of an extensive number of Z2 symmetries, which remain intact even in the presence of a quantum transverse magnetic field. We establish a general duality approach that restricts the quantum problem to a given sector of conserved Z2 charges and use it to study how the outcome of the quantum adiabatic algorithm depends on the hypergraph geometry. We show that the tree hypergraph which corresponds to a classically solvable instance of the 3-XORSAT problem features a constant gap, whereas the closed hypergraph encounters a second-order phase transition with a gap vanishing as a power-law in the problem size. The duality developed in this work provides a practical tool for studies of quantum models with classically degenerate energy manifold and reveals potential connections between glasses and gauge theories.
Publishing Year
Date Published
2021-12-14
Journal Title
Physical Review A
Acknowledgement
We would like to thank S. De Nicola, A. Michaidilis, T. Gulden, Y. Nez-Fernndez, P. Brighi, and S. Sack for fruitful discussions and valuable feedback on the manuscript. M.S. acknowledges useful discussions with E. Altman, L. Cugliandolo, and C. Laumann. We acknowledge support from the European Research Council (ERC) under the European Union's Horizon 2020 Research and Innovation Programme Grant Agreement No. 850899.
Volume
104
Issue
6
Article Number
062423
ISSN
eISSN
IST-REx-ID

Cite this

Medina Ramos RA, Serbyn M. Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT). Physical Review A. 2021;104(6). doi:10.1103/physreva.104.062423
Medina Ramos, R. A., & Serbyn, M. (2021). Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT). Physical Review A. American Physical Society. https://doi.org/10.1103/physreva.104.062423
Medina Ramos, Raimel A, and Maksym Serbyn. “Duality Approach to Quantum Annealing of the 3-Variable Exclusive-or Satisfiability Problem (3-XORSAT).” Physical Review A. American Physical Society, 2021. https://doi.org/10.1103/physreva.104.062423.
R. A. Medina Ramos and M. Serbyn, “Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT),” Physical Review A, vol. 104, no. 6. American Physical Society, 2021.
Medina Ramos RA, Serbyn M. 2021. Duality approach to quantum annealing of the 3-variable exclusive-or satisfiability problem (3-XORSAT). Physical Review A. 104(6), 062423.
Medina Ramos, Raimel A., and Maksym Serbyn. “Duality Approach to Quantum Annealing of the 3-Variable Exclusive-or Satisfiability Problem (3-XORSAT).” Physical Review A, vol. 104, no. 6, 062423, American Physical Society, 2021, doi:10.1103/physreva.104.062423.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2106.06344

Search this title in

Google Scholar