Clustering in Hilbert space of a quantum optimization problem

S. C. Morampudi, B. Hsu, Shivaji Lal Sondhi, R. Moessner, C. R. Laumann

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Article number042303
JournalPhysical Review A
Issue number4
StatePublished - Oct 5 2017

All Science Journal Classification (ASJC) codes

  • Atomic and Molecular Physics, and Optics


Dive into the research topics of 'Clustering in Hilbert space of a quantum optimization problem'. Together they form a unique fingerprint.

Cite this