Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1009.1635 · Lecture notes in physics

Statistical Mechanics of Classical and Quantum Computational Complexity

Chris R. Laumann, Roderich Moessner, Antonello Scardicchio, S. L. Sondhi

Published Jan 1, 2012• 3 citations
arXivHTMLPDF
DOI
10.1007/978-3-642-10449-7_7

Related papers

Statistical mechanics of disordered quantum optimization

Chris R. Laumann

The classical statistical mechanical approach to complexity theory proceeds from the study of ensembles of computationally intractable optimization problems as a species of unusual disordered magnetic systems. Over the last thirty years, researchers have used this approach to supplement worst-case hardness results encoded by complexity theory with detailed information about thermodynamic and dynamic phase transitions in the structure of typical cases. This exchange of ideas between classical statistical mechanics and computer science enabled the development of important heuristic algorithms such as simulated annealing and survey propagation and further refined our understanding of glassiness and critical slowing in physical disordered systems. In this thesis, we map out an analogous program in the quantum context. The question is simple: what can quantum statistical mechanics reveal about the difficulty of solving hard quantum optimization problems? Or more directly, what makes those problems hard even for quantum computers? In this pursuit, we introduce the study of ensembles of optimization problems whose complexity status is intrinsically quantum mechanical (Part I) and develop techniques to study quantum spin glasses and the transverse field adiabatic algorithm applied to classically hard random optimization problems (Part II). In particular, we introduce the study of random quantum satisfiability (QSAT) and identify the coarse aspects of its phase diagram, including a new form of entanglement transition. We generalize the cavity method to the study of quantum models and use it to study the transverse field Ising glass and frustrated AKLT models on the Bethe lattice. We further apply the cavity method to extract Griffiths-McCoy singularities in a diluted (classical) ferromagnet and finally observe that there are no Goldstone bosons on the Bethe lattice.

•Jan 1, 2010•1 citation

Computational Complexity in Statistical Physics

Jonathan L. Machta

APS•Mar 1, 2001•1 citation

Computational Complexity and Quantum Computing

Marco O. Lanzagorta, Jeffrey K. Uhlmann

Synthesis lectures on quantum computing•Jan 1, 2008•0 citations

General Quantum Theory: I ---- Deducing Quantum Physics and Solving Two Origin Crisises of Wave-Particle Duality and the First Quantization

Chen‐Bin Huang, Yong-Chang Huang, Jia-Min Song

Density distribution function of classical statistical mechanics is generally generalized as a product of a general complex function and its complex Hermitian conjugate function, and the average of classical statistical mechanics is generalized as the average of the quantum mechanics. Furthermore, this paper derives three ones of the five axiom presumptions of quantum mechanics, e.g., deduces Schrȍdinger equation by two general ways, makes the three axiom presumptions into three theorems of quantum mechanics, not only solves the crisis to hard understand, but also gets new theories and new discoveries, e.g., this paper solves the crisis of the origin of the wave-particle duality, derives operators, eigenvalues and eigenstates, deduces commutation relations for coordinate and momentum as well as the time and energy, and discovers quantum mechanics is just a generalization ( mechanics ) theory of the complex square root of ( real density function of ) classical statistical mechanics. Quantum mechanics being just a generalization theory of the complex square root of classical statistical mechanics is both new physics and revolutionary discovery, which are affecting people’s deep philosophical thinking for modern physics development, solve all the crisises of quantum mechanics, quantum information and so on, and make quantum mechanics have scientific solid bases being checked and both no basic axiom presumption and no all the quantum strange incomprehensible properties, because classical statistical mechanics and the complex square root of classical statistical mechanics have the scientific solid bases being checked. In addition, this paper discovers the reason no taking the time derivative of space coordinates in Schrȍdinger equation. Therefore, this paper gives solution to the crisis of the first quantization origin, and mainly deduces quantum physics no all the quantum current strange incomprehensible properties.

•Jan 5, 2021•1 citation

Quantum Computational Complexity

John Watrous

Springer eBooks•Nov 2, 2011•47 citations

Quantum correlations from incomplete classical statistics

CHRISTOF WETTERICH

We formulate incomplete classical statistics for situations where the knowledge about the probability distribution outside a local region is limited. The information needed to compute expectation values of local observables can be collected in a quantum mechanical state vector, whereas further statistical information about the probability distribution outside the local region becomes irrelevant. The translation of the available information between neighboring local regions is expressed by a Hamilton operator. A quantum mechanical operator can be associated to each local observable, such that expectation values of ``classical'' observables can be computed by the usual quantum mechanical rules. The requirement that correlation functions should respect equivalence relations for local obeservables induces a non-commutative product in classical statistics, in complete correspondence to the quantum mechanical operator product. We also discuss the issue of interference and the complex structure of quantum mechanics within our classical statistical setting.

arXiv:hep-th/0104074•Apr 9, 2001•0 citations
The classical statistical mechanical approach to complexity theory proceeds from the study of ensembles of computationally intractable optimization problems as a species of unusual disordered magnetic systems. Over the last thirty years, researchers have used this approach to supplement worst-case hardness results encoded by complexity theory with detailed information about thermodynamic and dynamic phase transitions in the structure of typical cases. This exchange of ideas between classical statistical mechanics and computer science enabled the development of important heuristic algorithms such as simulated annealing and survey propagation and further refined our understanding of glassiness and critical slowing in physical disordered systems. In this thesis, we map out an analogous program in the quantum context. The question is simple: what can quantum statistical mechanics reveal about the difficulty of solving hard quantum optimization problems? Or more directly, what makes those problems hard even for quantum computers? In this pursuit, we introduce the study of ensembles of optimization problems whose complexity status is intrinsically quantum mechanical (Part I) and develop techniques to study quantum spin glasses and the transverse field adiabatic algorithm applied to classically hard random optimization problems (Part II). In particular, we introduce the study of random quantum satisfiability (QSAT) and identify the coarse aspects of its phase diagram, including a new form of entanglement transition. We generalize the cavity method to the study of quantum models and use it to study the transverse field Ising glass and frustrated AKLT models on the Bethe lattice. We further apply the cavity method to extract Griffiths-McCoy singularities in a diluted (classical) ferromagnet and finally observe that there are no Goldstone bosons on the Bethe lattice.
Density distribution function of classical statistical mechanics is generally generalized as a product of a general complex function and its complex Hermitian conjugate function, and the average of classical statistical mechanics is generalized as the average of the quantum mechanics. Furthermore, this paper derives three ones of the five axiom presumptions of quantum mechanics, e.g., deduces Schrȍdinger equation by two general ways, makes the three axiom presumptions into three theorems of quantum mechanics, not only solves the crisis to hard understand, but also gets new theories and new discoveries, e.g., this paper solves the crisis of the origin of the wave-particle duality, derives operators, eigenvalues and eigenstates, deduces commutation relations for coordinate and momentum as well as the time and energy, and discovers quantum mechanics is just a generalization ( mechanics ) theory of the complex square root of ( real density function of ) classical statistical mechanics. Quantum mechanics being just a generalization theory of the complex square root of classical statistical mechanics is both new physics and revolutionary discovery, which are affecting people’s deep philosophical thinking for modern physics development, solve all the crisises of quantum mechanics, quantum information and so on, and make quantum mechanics have scientific solid bases being checked and both no basic axiom presumption and no all the quantum strange incomprehensible properties, because classical statistical mechanics and the complex square root of classical statistical mechanics have the scientific solid bases being checked. In addition, this paper discovers the reason no taking the time derivative of space coordinates in Schrȍdinger equation. Therefore, this paper gives solution to the crisis of the first quantization origin, and mainly deduces quantum physics no all the quantum current strange incomprehensible properties.
We formulate incomplete classical statistics for situations where the knowledge about the probability distribution outside a local region is limited. The information needed to compute expectation values of local observables can be collected in a quantum mechanical state vector, whereas further statistical information about the probability distribution outside the local region becomes irrelevant. The translation of the available information between neighboring local regions is expressed by a Hamilton operator. A quantum mechanical operator can be associated to each local observable, such that expectation values of ``classical'' observables can be computed by the usual quantum mechanical rules. The requirement that correlation functions should respect equivalence relations for local obeservables induces a non-commutative product in classical statistics, in complete correspondence to the quantum mechanical operator product. We also discuss the issue of interference and the complex structure of quantum mechanics within our classical statistical setting.