Computational Phase Transition Signature in Gibbs Sampling

H. Philathong; I. Zacharov; J. Biamonte; V. Akshay

arxiv: 1906.10705 · v1 · pith:AQYU7AOYnew · submitted 2019-06-25 · 🪐 quant-ph · cond-mat.dis-nn· cond-mat.stat-mech· cs.CC· cs.LG

Computational Phase Transition Signature in Gibbs Sampling

H. Philathong , V. Akshay , I. Zacharov , J. Biamonte This is my paper

Pith reviewed 2026-05-25 16:21 UTC · model grok-4.3

classification 🪐 quant-ph cond-mat.dis-nncond-mat.stat-mechcs.CCcs.LG

keywords Gibbs samplingphase transitionsatisfiabilitycomputational complexityquantum annealingstochastic annealingphysical computationprobability distribution

0 comments

The pith

The computational phase transition in satisfiability problems produces a detectable signature in Gibbs distributions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the abrupt shift in computational resources needed for decision problems like propositional satisfiability at a critical constraint-to-variable ratio also appears as a feature in the probability distributions generated by Gibbs sampling. This connection matters because physics-based processors embed such problems and evolve physical systems to sample from these distributions. A sympathetic reader would see value in the claim that the phase transition can therefore be observed directly through physical measurements of the output ensemble rather than only through algorithmic runtime statistics. The work simulates an experiment that would realize this observation in annealing hardware.

Core claim

At a critical constraint to variable ratio, decision problems such as propositional satisfiability appear to statistically exhibit an abrupt transition in required computational resources. This algorithmic phase transition admits a signature in Gibbs distributions, and the paper predicts and prescribes the physical observation of this effect in processors that embed problem instances and evolve a physical system into an ensemble to recover a probability distribution.

What carries the argument

The signature of the algorithmic phase transition within the Gibbs distribution of a physical processor.

If this is right

Physics-based processors could observe the computational phase transition directly from their output distributions.
The hardness jump at the transition point becomes accessible without separate algorithmic runtime measurements.
Experimental realization of the predicted signature would link computational complexity features to measurable physical ensembles.
Gibbs sampling algorithms implemented in hardware would inherit an observable marker of the underlying decision-problem transition.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the signature is confirmed, hardware design choices that alter embedding might still preserve the transition feature in the sampled distribution.
Similar signatures could be sought in other computational transitions, such as those appearing in optimization or counting problems.
The result suggests a route to test whether non-equilibrium effects in real devices obscure or enhance the equilibrium signature.

Load-bearing premise

The algorithmic phase transition in resource requirements directly produces an observable signature in the equilibrium Gibbs distribution of a physical processor, independent of embedding details or non-equilibrium dynamics.

What would settle it

Prepare SAT instances at and away from the critical clause-to-variable ratio, sample their Gibbs distributions on a physical or simulated annealing device, and check whether a predicted change in distribution properties such as entropy or probability concentration appears only at the critical ratio.

Figures

Figures reproduced from arXiv: 1906.10705 by H. Philathong, I. Zacharov, J. Biamonte, V. Akshay.

**Figure 1.** Figure 1: (Top): Percent of satisfiable instances (left axis) and run-time (right axis)) versus clause density. Varying clause [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

**Figure 2.** Figure 2: (Top): Occupancy of the thermal ground state corresponding to Hamiltonians embedding 2-SAT instances (left) and [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗

read the original abstract

Gibbs sampling is fundamental to a wide range of computer algorithms. Such algorithms are set to be replaced by physics based processors$-$be it quantum or stochastic annealing devices$-$which embed problem instances and evolve a physical system into an ensemble to recover a probability distribution. At a critical constraint to variable ratio, decision problems$-$such as propositional satisfiability$-$appear to statistically exhibit an abrupt transition in required computational resources. This so called, algorithmic or computational phase transition signature, has yet-to-be observed in contemporary physics based processors. We found that the computational phase transition admits a signature in Gibbs' distributions and hence we predict and prescribe the physical observation of this effect. We simulate such an experiment, that when realized experimentally, we believe would represent a milestone in the physical theory of computation.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims a signature of the SAT computational phase transition appears directly in the equilibrium Gibbs distribution of physical samplers, but the link between algorithmic hardness and static distributional features looks unproven.

read the letter

The paper takes the established computational phase transition in random SAT at the critical clause-to-variable ratio and asks whether it produces a measurable feature in the Gibbs distribution that annealing hardware would sample. They run a simulation that prescribes what an experiment on a physical processor should look like and claim this would be a milestone observation. That mapping attempt is the main new element; prior work has discussed the algorithmic transition and separate work has studied physical samplers, but tying the two via an equilibrium signature is a distinct step. The simulation itself is concrete enough to give experimenters something to try. The soft spot is the central assumption that algorithmic hardness at the transition must imprint on the static form of the target distribution. Hardness usually arises from solution-space geometry or barriers that affect how long it takes to equilibrate or to mix, not from a sharp change in the equilibrium probabilities or their low-order moments. If quantities like energy fluctuations or pairwise correlations vary smoothly across the critical ratio, the proposed signature would not appear. The abstract and stress-test note give no equations showing how the transition enters the distribution, so it is unclear whether the simulation actually demonstrates an independent physical effect or just reproduces the known algorithmic change in a different language. This is for people working on quantum or stochastic annealing hardware who want to connect complexity results to measurable device statistics. It is coherent enough on its own terms to deserve referee time, even if the mapping needs substantial tightening.

Referee Report

2 major / 0 minor

Summary. The manuscript claims that the computational (algorithmic) phase transition in decision problems such as SAT—at a critical constraint-to-variable ratio—admits a detectable signature directly in the equilibrium Gibbs distribution. The authors assert they have identified this signature, simulate a corresponding experiment on a physics-based processor (quantum or stochastic annealing), and predict that its physical realization would constitute a milestone in the physical theory of computation.

Significance. If substantiated, the result would provide a direct physical observable for algorithmic hardness, linking computational complexity theory to equilibrium statistical mechanics in a manner independent of embedding details or non-equilibrium dynamics. This would be a notable contribution if the simulation demonstrates a sharp, falsifiable feature in the distribution at the critical ratio.

major comments (2)

[Abstract / central claim] The central claim—that the algorithmic phase transition produces an observable signature in the static equilibrium Gibbs distribution itself—rests on an unexamined assumption. Algorithmic hardness at the critical ratio typically arises from the structure of the solution space or from barriers that affect sampling dynamics and resource requirements, not necessarily from changes in the form, moments, or correlations of the target equilibrium distribution. No argument is supplied showing why observables such as energy fluctuations or spin correlations would exhibit a non-smooth feature precisely at the critical ratio independent of the physical embedding.
[Simulation description] The simulation is described only at the level of the abstract (a prediction that the effect can be observed). No model Hamiltonian, choice of observables, quantitative measure of the purported signature, or comparison against the critical ratio is provided, preventing assessment of whether the simulated data actually isolates an equilibrium feature attributable to the computational transition rather than to finite-size effects or annealing schedule.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive comments. We respond point-by-point to the major comments below.

read point-by-point responses

Referee: The central claim—that the algorithmic phase transition produces an observable signature in the static equilibrium Gibbs distribution itself—rests on an unexamined assumption. Algorithmic hardness at the critical ratio typically arises from the structure of the solution space or from barriers that affect sampling dynamics and resource requirements, not necessarily from changes in the form, moments, or correlations of the target equilibrium distribution. No argument is supplied showing why observables such as energy fluctuations or spin correlations would exhibit a non-smooth feature precisely at the critical ratio independent of the physical embedding.

Authors: The manuscript links the computational phase transition to changes in solution-space structure (e.g., the onset of clustering of satisfying assignments), which directly alters the equilibrium measure and induces non-analyticities in observables such as spin correlations and energy fluctuations. This connection is embedding-independent because it follows from the statistical properties of the random ensemble at the critical ratio. We will add an explicit paragraph deriving the expected discontinuity in the two-point correlation function to make the argument self-contained. revision: yes
Referee: The simulation is described only at the level of the abstract (a prediction that the effect can be observed). No model Hamiltonian, choice of observables, quantitative measure of the purported signature, or comparison against the critical ratio is provided, preventing assessment of whether the simulated data actually isolates an equilibrium feature attributable to the computational transition rather than to finite-size effects or annealing schedule.

Authors: We agree the simulation description is too brief. The revised manuscript will specify the Ising Hamiltonian obtained from the standard 3-SAT embedding, the measured observables (energy variance and spin-spin correlations), the quantitative signature (susceptibility peak), and direct comparison of its location against the known critical ratio α_c ≈ 4.26, together with finite-size scaling to confirm the feature is not an artifact of dynamics or system size. revision: yes

Circularity Check

0 steps flagged

No circularity: claim of signature is observational proposal, not self-referential derivation

full rationale

The paper asserts that a computational phase transition admits a signature in Gibbs distributions, leading to a prediction of physical observability. However, the abstract and available text contain no equations, fitted parameters, or self-citations that reduce this claim to its inputs by construction. No load-bearing step equates a 'prediction' to a prior fit or renames an input as output. The central claim is presented as an empirical finding to be tested experimentally, remaining self-contained against external benchmarks without internal circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities; ledger is empty by default.

pith-pipeline@v0.9.0 · 5683 in / 946 out tokens · 34716 ms · 2026-05-25T16:21:22.449692+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 1 internal anchor

[1]

Quantum theory, the Church–Turing principle and the universal quantum computer.Proceedings of the Royal Society of London

David Deutsch. Quantum theory, the Church–Turing principle and the universal quantum computer.Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818):97–117, 1985

work page 1985
[2]

An unsolvable problem of elementary number theory.American journal of mathematics, 58(2):345–363, 1936

Alonzo Church. An unsolvable problem of elementary number theory.American journal of mathematics, 58(2):345–363, 1936

work page 1936
[3]

On computable numbers, with an application to the Entscheidungsproblem.Proceedings of the London mathematical society, 2(1):230–265, 1937

Alan Mathison Turing. On computable numbers, with an application to the Entscheidungsproblem.Proceedings of the London mathematical society, 2(1):230–265, 1937

work page 1937
[4]

Experimental results on the crossover point in random 3-SAT

James M Crawford and Larry D Auton. Experimental results on the crossover point in random 3-SAT. InArtiﬁcial Intelligence, volume 81, pages 31–57, 1996

work page 1996
[5]

Sharp thresholds of graph properties, and the k-SAT problem.Journal of the American mathematical Society, 12(4):1017–1054, 1999

Ehud Friedgut, Jean Bourgain, et al. Sharp thresholds of graph properties, and the k-SAT problem.Journal of the American mathematical Society, 12(4):1017–1054, 1999. 5 0 1 2 3 4 5 6 0.0 0.2 0.4 0.6 0.8 1.0( min, ) 0 2 4 6 8 10 0.0 0.2 0.4 0.6 0.8 1.0 Satisfiability Probability classical = 3 = 2 = 1 0 1 2 3 4 5 6 Clause Density 0 1 2 3 4 5 6 7min 0 2 4 6 8...

work page 1999
[6]

Critical behavior in the computational cost of satisﬁability testing.Artiﬁcial Intelli- gence, 81(1-2):273–295, 1996

Bart Selman and Scott Kirkpatrick. Critical behavior in the computational cost of satisﬁability testing.Artiﬁcial Intelli- gence, 81(1-2):273–295, 1996

work page 1996
[7]

Ising formulations of many np problems.Frontiers in Physics, 2:5, 2014

Andrew Lucas. Ising formulations of many np problems.Frontiers in Physics, 2:5, 2014

work page 2014
[8]

Nonperturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins.Physical Review A, 77(5):052331, 2008

JD Biamonte. Nonperturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins.Physical Review A, 77(5):052331, 2008

work page 2008
[9]

Ground-state spin logic.EPL (Europhysics Letters), 99(5):57004, 2012

James Daniel Whitﬁeld, Mauro Faccin, and JD Biamonte. Ground-state spin logic.EPL (Europhysics Letters), 99(5):57004, 2012

work page 2012
[10]

Optimization by simulated annealing.Science, 220(4598):671–680, 1983

Scott Kirkpatrick, Daniel C Gelatt, and Mario P Vecchi. Optimization by simulated annealing.Science, 220(4598):671–680, 1983

work page 1983
[11]

Mapping of Ising models onto injection-locked laser systems

Shoko Utsunomiya, Kenta Takata, and Yoshihisa Yamamoto. Mapping of Ising models onto injection-locked laser systems. Optics express, 19(19):18091–18108, 2011

work page 2011
[12]

A coherent Ising machine for 2000-node optimization problems

Takahiro Inagaki, Yoshitaka Haribara, Koji Igarashi, Tomohiro Sonobe, Shuhei Tamate, Toshimori Honjo, Alireza Marandi, Peter L McMahon, Takeshi Umeki, Koji Enbutsu, et al. A coherent Ising machine for 2000-node optimization problems. Science, 354(6312):603–606, 2016

work page 2000
[13]

Large-scale photonic ising machine by spatial light modulation.Physical Review Letters, 122(21):213902, 2019

D Pierangeli, G Marcucci, and C Conti. Large-scale photonic ising machine by spatial light modulation.Physical Review Letters, 122(21):213902, 2019

work page 2019
[14]

Network of time-multiplexed optical parametric oscillators as a coherent Ising machine.Nature Photonics, 8(12):937, 2014

Alireza Marandi, Zhe Wang, Kenta Takata, Robert L Byer, and Yoshihisa Yamamoto. Network of time-multiplexed optical parametric oscillators as a coherent Ising machine.Nature Photonics, 8(12):937, 2014

work page 2014
[15]

Observing geometric frustration with thousands of coupled lasers

Micha Nixon, Eitan Ronen, Asher A Friesem, and Nir Davidson. Observing geometric frustration with thousands of coupled lasers. Physical review letters, 110(18):184102, 2013

work page 2013
[16]

Realizing the classical XY Hamiltonian in polariton simulators

Natalia G Berloﬀ, Matteo Silva, Kirill Kalinin, Alexis Askitopoulos, Julian D Töpfer, Pasquale Cilibrizzi, Wolfgang Langbein, and Pavlos G Lagoudakis. Realizing the classical XY Hamiltonian in polariton simulators. Nature materi- 6 als, 16(11):1120, 2017

work page 2017
[17]

Variable potentials for thermalized light and coupled condensates.Nature Photonics, 11(9):565, 2017

David Dung, Christian Kurtscheid, Tobias Damm, Julian Schmitt, Frank Vewinger, Martin Weitz, and Jan Klaers. Variable potentials for thermalized light and coupled condensates.Nature Photonics, 11(9):565, 2017

work page 2017
[18]

Global optimization of spin Hamiltonians with gain-dissipative systems.Scientiﬁc reports, 8(1):17791, 2018

Kirill Kalinin and Natalia G Berloﬀ. Global optimization of spin Hamiltonians with gain-dissipative systems.Scientiﬁc reports, 8(1):17791, 2018

work page 2018
[19]

Quantum annealing with manufactured spins.Nature, 473(7346):194, 2011

Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, R Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. Quantum annealing with manufactured spins.Nature, 473(7346):194, 2011

work page 2011
[20]

Digitized adiabatic quantum computing with a superconducting circuit.Nature, 534(7606):222, 2016

RamiBarends, AlirezaShabani, LucasLamata, JulianKelly, AntonioMezzacapo, UrtziLasHeras, RyanBabbush, AustinG Fowler, Brooks Campbell, Yu Chen, et al. Digitized adiabatic quantum computing with a superconducting circuit.Nature, 534(7606):222, 2016

work page 2016
[21]

Experimental demonstration of a robust and scalable ﬂux qubit.Physical Review B, 81(13):134510, 2010

R Harris, J Johansson, AJ Berkley, MW Johnson, T Lanting, Siyuan Han, P Bunyk, E Ladizinsky, T Oh, I Perminov, et al. Experimental demonstration of a robust and scalable ﬂux qubit.Physical Review B, 81(13):134510, 2010

work page 2010
[22]

Phase transitions in a programmable quantum spin glass simulator.Science, 361(6398):162–165, 2018

R Harris, Y Sato, AJ Berkley, M Reis, F Altomare, MH Amin, K Boothby, P Bunyk, C Deng, C Enderud, et al. Phase transitions in a programmable quantum spin glass simulator.Science, 361(6398):162–165, 2018

work page 2018
[23]

Observation of topological phenomena in a programmable lattice of 1,800 qubits

Andrew D King, Juan Carrasquilla, Jack Raymond, Isil Ozﬁdan, Evgeny Andriyash, Andrew Berkley, Mauricio Reis, Trevor Lanting, Richard Harris, Fabio Altomare, et al. Observation of topological phenomena in a programmable lattice of 1,800 qubits. Nature, 560(7719):456, 2018

work page 2018
[24]

The complexity of theorem-proving procedures

Stephen A Cook. The complexity of theorem-proving procedures. InProceedings of the third annual ACM symposium on Theory of computing, pages 151–158. ACM, 1971

work page 1971
[25]

Generating hard satisﬁability problems.Artiﬁcial intelligence, 81(1-2):17–29, 1996

Bart Selman, David G Mitchell, and Hector J Levesque. Generating hard satisﬁability problems.Artiﬁcial intelligence, 81(1-2):17–29, 1996

work page 1996
[26]

The decision problem for a class of ﬁrst-order formulas in which all disjunctions are binary.Mathematical Logic Quarterly, 13(1-2):15–20, 1967

Melven R Krom. The decision problem for a class of ﬁrst-order formulas in which all disjunctions are binary.Mathematical Logic Quarterly, 13(1-2):15–20, 1967

work page 1967
[27]

The scaling window of the 2-SAT transition

Béla Bollobás, Christian Borgs, Jennifer T Chayes, Jeong Han Kim, and David B Wilson. The scaling window of the 2-SAT transition. Random Structures & Algorithms, 18(3):201–256, 2001

work page 2001
[28]

Mick gets some (the odds are on his side)(satisﬁability)

Vašek Chvátal and Bruce Reed. Mick gets some (the odds are on his side)(satisﬁability). InProceedings., 33rd Annual Symposium on Foundations of Computer Science, pages 620–627. IEEE, 1992

work page 1992
[29]

A threshold for unsatisﬁability.Journal of Computer and System Sciences, 53(3):469–486, 1996

Andreas Goerdt. A threshold for unsatisﬁability.Journal of Computer and System Sciences, 53(3):469–486, 1996

work page 1996
[30]

PicoSAT essentials.Journal on Satisﬁability, Boolean Modeling and Computation, 4:75–97, 2008

Armin Biere. PicoSAT essentials.Journal on Satisﬁability, Boolean Modeling and Computation, 4:75–97, 2008

work page 2008
[31]

The Satisfiability Threshold of Random 3-SAT Is at Least 3.52

Mohammad Taghi Hajiaghayi and Gregory B Sorkin. The satisﬁability threshold of random 3-SAT is at least 3.52.arXiv preprint math/0310193, 2003

work page internal anchor Pith review Pith/arXiv arXiv 2003
[32]

On the satisﬁability threshold and clustering of solutions of random 3-SAT formulas

Elitza Maneva and Alistair Sinclair. On the satisﬁability threshold and clustering of solutions of random 3-SAT formulas. Theoretical Computer Science, 407(1-3):359–369, 2008

work page 2008
[33]

Zacharov, R

I. Zacharov, R. Arslanov, M. Gunin, D. Stefonishin, S. Pavlov, O. Panarin, A. Maliutin, S. Rykovanov, and M. Fedorov. ‘Zhores’ – Petaﬂops Supercomputer for Data-Driven Modeling, Machine Learning and Artiﬁcial Intelligence, feb 2019

work page 2019
[34]

On the computational complexity of Ising spin glass models.Journal of Physics A: Mathematical and General, 15(10):3241, 1982

Francisco Barahona. On the computational complexity of Ising spin glass models.Journal of Physics A: Mathematical and General, 15(10):3241, 1982. Appendix: Ising Spin Embedding Finding ground energy and ground state conﬁgurations of physical systems such as spin glasses isNP-hard [34]. 2-SAT and 3-SAT instances can be directly mapped onto the Hamiltonian ...

work page 1982

[1] [1]

Quantum theory, the Church–Turing principle and the universal quantum computer.Proceedings of the Royal Society of London

David Deutsch. Quantum theory, the Church–Turing principle and the universal quantum computer.Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 400(1818):97–117, 1985

work page 1985

[2] [2]

An unsolvable problem of elementary number theory.American journal of mathematics, 58(2):345–363, 1936

Alonzo Church. An unsolvable problem of elementary number theory.American journal of mathematics, 58(2):345–363, 1936

work page 1936

[3] [3]

On computable numbers, with an application to the Entscheidungsproblem.Proceedings of the London mathematical society, 2(1):230–265, 1937

Alan Mathison Turing. On computable numbers, with an application to the Entscheidungsproblem.Proceedings of the London mathematical society, 2(1):230–265, 1937

work page 1937

[4] [4]

Experimental results on the crossover point in random 3-SAT

James M Crawford and Larry D Auton. Experimental results on the crossover point in random 3-SAT. InArtiﬁcial Intelligence, volume 81, pages 31–57, 1996

work page 1996

[5] [5]

Sharp thresholds of graph properties, and the k-SAT problem.Journal of the American mathematical Society, 12(4):1017–1054, 1999

Ehud Friedgut, Jean Bourgain, et al. Sharp thresholds of graph properties, and the k-SAT problem.Journal of the American mathematical Society, 12(4):1017–1054, 1999. 5 0 1 2 3 4 5 6 0.0 0.2 0.4 0.6 0.8 1.0( min, ) 0 2 4 6 8 10 0.0 0.2 0.4 0.6 0.8 1.0 Satisfiability Probability classical = 3 = 2 = 1 0 1 2 3 4 5 6 Clause Density 0 1 2 3 4 5 6 7min 0 2 4 6 8...

work page 1999

[6] [6]

Critical behavior in the computational cost of satisﬁability testing.Artiﬁcial Intelli- gence, 81(1-2):273–295, 1996

Bart Selman and Scott Kirkpatrick. Critical behavior in the computational cost of satisﬁability testing.Artiﬁcial Intelli- gence, 81(1-2):273–295, 1996

work page 1996

[7] [7]

Ising formulations of many np problems.Frontiers in Physics, 2:5, 2014

Andrew Lucas. Ising formulations of many np problems.Frontiers in Physics, 2:5, 2014

work page 2014

[8] [8]

Nonperturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins.Physical Review A, 77(5):052331, 2008

JD Biamonte. Nonperturbative k-body to two-body commuting conversion Hamiltonians and embedding problem instances into Ising spins.Physical Review A, 77(5):052331, 2008

work page 2008

[9] [9]

Ground-state spin logic.EPL (Europhysics Letters), 99(5):57004, 2012

James Daniel Whitﬁeld, Mauro Faccin, and JD Biamonte. Ground-state spin logic.EPL (Europhysics Letters), 99(5):57004, 2012

work page 2012

[10] [10]

Optimization by simulated annealing.Science, 220(4598):671–680, 1983

Scott Kirkpatrick, Daniel C Gelatt, and Mario P Vecchi. Optimization by simulated annealing.Science, 220(4598):671–680, 1983

work page 1983

[11] [11]

Mapping of Ising models onto injection-locked laser systems

Shoko Utsunomiya, Kenta Takata, and Yoshihisa Yamamoto. Mapping of Ising models onto injection-locked laser systems. Optics express, 19(19):18091–18108, 2011

work page 2011

[12] [12]

A coherent Ising machine for 2000-node optimization problems

Takahiro Inagaki, Yoshitaka Haribara, Koji Igarashi, Tomohiro Sonobe, Shuhei Tamate, Toshimori Honjo, Alireza Marandi, Peter L McMahon, Takeshi Umeki, Koji Enbutsu, et al. A coherent Ising machine for 2000-node optimization problems. Science, 354(6312):603–606, 2016

work page 2000

[13] [13]

Large-scale photonic ising machine by spatial light modulation.Physical Review Letters, 122(21):213902, 2019

D Pierangeli, G Marcucci, and C Conti. Large-scale photonic ising machine by spatial light modulation.Physical Review Letters, 122(21):213902, 2019

work page 2019

[14] [14]

Network of time-multiplexed optical parametric oscillators as a coherent Ising machine.Nature Photonics, 8(12):937, 2014

Alireza Marandi, Zhe Wang, Kenta Takata, Robert L Byer, and Yoshihisa Yamamoto. Network of time-multiplexed optical parametric oscillators as a coherent Ising machine.Nature Photonics, 8(12):937, 2014

work page 2014

[15] [15]

Observing geometric frustration with thousands of coupled lasers

Micha Nixon, Eitan Ronen, Asher A Friesem, and Nir Davidson. Observing geometric frustration with thousands of coupled lasers. Physical review letters, 110(18):184102, 2013

work page 2013

[16] [16]

Realizing the classical XY Hamiltonian in polariton simulators

Natalia G Berloﬀ, Matteo Silva, Kirill Kalinin, Alexis Askitopoulos, Julian D Töpfer, Pasquale Cilibrizzi, Wolfgang Langbein, and Pavlos G Lagoudakis. Realizing the classical XY Hamiltonian in polariton simulators. Nature materi- 6 als, 16(11):1120, 2017

work page 2017

[17] [17]

Variable potentials for thermalized light and coupled condensates.Nature Photonics, 11(9):565, 2017

David Dung, Christian Kurtscheid, Tobias Damm, Julian Schmitt, Frank Vewinger, Martin Weitz, and Jan Klaers. Variable potentials for thermalized light and coupled condensates.Nature Photonics, 11(9):565, 2017

work page 2017

[18] [18]

Global optimization of spin Hamiltonians with gain-dissipative systems.Scientiﬁc reports, 8(1):17791, 2018

Kirill Kalinin and Natalia G Berloﬀ. Global optimization of spin Hamiltonians with gain-dissipative systems.Scientiﬁc reports, 8(1):17791, 2018

work page 2018

[19] [19]

Quantum annealing with manufactured spins.Nature, 473(7346):194, 2011

Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, R Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. Quantum annealing with manufactured spins.Nature, 473(7346):194, 2011

work page 2011

[20] [20]

Digitized adiabatic quantum computing with a superconducting circuit.Nature, 534(7606):222, 2016

RamiBarends, AlirezaShabani, LucasLamata, JulianKelly, AntonioMezzacapo, UrtziLasHeras, RyanBabbush, AustinG Fowler, Brooks Campbell, Yu Chen, et al. Digitized adiabatic quantum computing with a superconducting circuit.Nature, 534(7606):222, 2016

work page 2016

[21] [21]

Experimental demonstration of a robust and scalable ﬂux qubit.Physical Review B, 81(13):134510, 2010

R Harris, J Johansson, AJ Berkley, MW Johnson, T Lanting, Siyuan Han, P Bunyk, E Ladizinsky, T Oh, I Perminov, et al. Experimental demonstration of a robust and scalable ﬂux qubit.Physical Review B, 81(13):134510, 2010

work page 2010

[22] [22]

Phase transitions in a programmable quantum spin glass simulator.Science, 361(6398):162–165, 2018

R Harris, Y Sato, AJ Berkley, M Reis, F Altomare, MH Amin, K Boothby, P Bunyk, C Deng, C Enderud, et al. Phase transitions in a programmable quantum spin glass simulator.Science, 361(6398):162–165, 2018

work page 2018

[23] [23]

Observation of topological phenomena in a programmable lattice of 1,800 qubits

Andrew D King, Juan Carrasquilla, Jack Raymond, Isil Ozﬁdan, Evgeny Andriyash, Andrew Berkley, Mauricio Reis, Trevor Lanting, Richard Harris, Fabio Altomare, et al. Observation of topological phenomena in a programmable lattice of 1,800 qubits. Nature, 560(7719):456, 2018

work page 2018

[24] [24]

The complexity of theorem-proving procedures

Stephen A Cook. The complexity of theorem-proving procedures. InProceedings of the third annual ACM symposium on Theory of computing, pages 151–158. ACM, 1971

work page 1971

[25] [25]

Generating hard satisﬁability problems.Artiﬁcial intelligence, 81(1-2):17–29, 1996

Bart Selman, David G Mitchell, and Hector J Levesque. Generating hard satisﬁability problems.Artiﬁcial intelligence, 81(1-2):17–29, 1996

work page 1996

[26] [26]

The decision problem for a class of ﬁrst-order formulas in which all disjunctions are binary.Mathematical Logic Quarterly, 13(1-2):15–20, 1967

Melven R Krom. The decision problem for a class of ﬁrst-order formulas in which all disjunctions are binary.Mathematical Logic Quarterly, 13(1-2):15–20, 1967

work page 1967

[27] [27]

The scaling window of the 2-SAT transition

Béla Bollobás, Christian Borgs, Jennifer T Chayes, Jeong Han Kim, and David B Wilson. The scaling window of the 2-SAT transition. Random Structures & Algorithms, 18(3):201–256, 2001

work page 2001

[28] [28]

Mick gets some (the odds are on his side)(satisﬁability)

Vašek Chvátal and Bruce Reed. Mick gets some (the odds are on his side)(satisﬁability). InProceedings., 33rd Annual Symposium on Foundations of Computer Science, pages 620–627. IEEE, 1992

work page 1992

[29] [29]

A threshold for unsatisﬁability.Journal of Computer and System Sciences, 53(3):469–486, 1996

Andreas Goerdt. A threshold for unsatisﬁability.Journal of Computer and System Sciences, 53(3):469–486, 1996

work page 1996

[30] [30]

PicoSAT essentials.Journal on Satisﬁability, Boolean Modeling and Computation, 4:75–97, 2008

Armin Biere. PicoSAT essentials.Journal on Satisﬁability, Boolean Modeling and Computation, 4:75–97, 2008

work page 2008

[31] [31]

The Satisfiability Threshold of Random 3-SAT Is at Least 3.52

Mohammad Taghi Hajiaghayi and Gregory B Sorkin. The satisﬁability threshold of random 3-SAT is at least 3.52.arXiv preprint math/0310193, 2003

work page internal anchor Pith review Pith/arXiv arXiv 2003

[32] [32]

On the satisﬁability threshold and clustering of solutions of random 3-SAT formulas

Elitza Maneva and Alistair Sinclair. On the satisﬁability threshold and clustering of solutions of random 3-SAT formulas. Theoretical Computer Science, 407(1-3):359–369, 2008

work page 2008

[33] [33]

Zacharov, R

I. Zacharov, R. Arslanov, M. Gunin, D. Stefonishin, S. Pavlov, O. Panarin, A. Maliutin, S. Rykovanov, and M. Fedorov. ‘Zhores’ – Petaﬂops Supercomputer for Data-Driven Modeling, Machine Learning and Artiﬁcial Intelligence, feb 2019

work page 2019

[34] [34]

On the computational complexity of Ising spin glass models.Journal of Physics A: Mathematical and General, 15(10):3241, 1982

Francisco Barahona. On the computational complexity of Ising spin glass models.Journal of Physics A: Mathematical and General, 15(10):3241, 1982. Appendix: Ising Spin Embedding Finding ground energy and ground state conﬁgurations of physical systems such as spin glasses isNP-hard [34]. 2-SAT and 3-SAT instances can be directly mapped onto the Hamiltonian ...

work page 1982