Duality approach to quantum annealing of the 3-XORSAT problem

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 $Z_2$ 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 $Z_2$ 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.

References in corpus (9)

• How Powerful is Adiabatic Quantum Computation?
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• Efficient simulation of infinite tree tensor network states on the Bethe lattice
• Cavity method for quantum spin glasses on the Bethe lattice
• The Quantum Transverse Field Ising Model on an Infinite Tree from Matrix Product States
• Clustering of non-ergodic eigenstates in quantum spin glasses
• Quantum annealing: the fastest route to quantum computation?
• Alternative solutions to diluted p-spin models and XORSAT problems

Cited by in corpus (1)

• Boundary conditions dependence of the phase transition in the quantum Newman-Moore model