Clustering in Hilbert space of a quantum optimization problem

S. C. Morampudi, B. Hsu, S. L. Sondhi, R. Moessner, and C. R. Laumann
Phys. Rev. A 96, 042303 – Published 5 October 2017

Abstract

The solution space of many classical optimization problems breaks up into clusters which are extensively distant from one another in the Hamming metric. Here, we show that an analogous quantum clustering phenomenon takes place in the ground-state subspace of a certain quantum optimization problem. This involves extending the notion of clustering to Hilbert space, where the classical Hamming distance is not immediately useful. Quantum clusters correspond to macroscopically distinct subspaces of the full quantum ground-state space which grow with the system size. We explicitly demonstrate that such clusters arise in the solution space of random quantum satisfiability (3-QSAT) at its satisfiability transition. We estimate both the number of these clusters and their internal entropy. The former are given by the number of hard-core dimer coverings of the core of the interaction graph, while the latter is related to the underconstrained degrees of freedom not touched by the dimers. We additionally provide numerical evidence suggesting that the 3-QSAT satisfiability transition may coincide with the product satisfiability transition, which would imply the absence of an intermediate entangled satisfiable phase.

  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Figure
  • Received 1 April 2017

DOI:https://doi.org/10.1103/PhysRevA.96.042303

©2017 American Physical Society

Physics Subject Headings (PhySH)

Statistical Physics & ThermodynamicsQuantum Information, Science & TechnologyCondensed Matter, Materials & Applied Physics

Authors & Affiliations

S. C. Morampudi1,2, B. Hsu3, S. L. Sondhi3, R. Moessner2, and C. R. Laumann1

  • 1Department of Physics, Boston University, Boston, Massachusetts 02215, USA
  • 2Max Planck Institut fur Physik komplexer Systeme, 01187 Dresden, Germany
  • 3Department of Physics, Princeton University, Princeton, New Jersey 08544, USA

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 96, Iss. 4 — October 2017

Reuse & Permissions
Access Options
CHORUS

Article Available via CHORUS

Download Accepted Manuscript
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×