Solvable Model of Quantum Random Optimization Problems

Laura Foini, Guilhem Semerjian, and Francesco Zamponi
Phys. Rev. Lett. 105, 167204 – Published 12 October 2010

Abstract

We study the quantum version of a simplified model of optimization problems, where quantum fluctuations are introduced by a transverse field acting on the qubits. We find a complex low-energy spectrum of the quantum Hamiltonian, characterized by an abrupt condensation transition and a continuum of level crossings as a function of the transverse field. We expect this complex structure to have deep consequences on the behavior of quantum algorithms attempting to find solutions to these problems.

  • Figure
  • Figure
  • Figure
  • Received 25 June 2010

DOI:https://doi.org/10.1103/PhysRevLett.105.167204

© 2010 The American Physical Society

Authors & Affiliations

Laura Foini1,2, Guilhem Semerjian1, and Francesco Zamponi1

  • 1LPTENS, CNRS UMR 8549, associée à l’UPMC Paris 06, 24 Rue Lhomond, 75005 Paris, France
  • 2SISSA and INFN, Sezione di Trieste, via Bonomea 265, I-34136 Trieste, Italy

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 105, Iss. 16 — 15 October 2010

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×