Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm (2008)
Young, A. P., Knysh, S., Smelyanskiy, V. N.
We study the minimum gap in the quantum version of the Exact Cover problem using Quantum Monte Carlo simulations, with a view to understanding the complexity of the quantum adiabatic algorithm for...
Statistical Mechanics of the Quantum K-Satisfiability problem (2008)
We study the quantum version of the random $K$-Satisfiability problem in the presence of the external magnetic field $\Gamma$ applied in the transverse direction. We derive the replica-symmetric free...
In this paper we show that the performance of the quantum adiabatic algorithm is determined by phase transitions in underlying problem in the presence of transverse magnetic field $\Gamma$. We show...
Adiabatic Quantum Computing in systems with constant inter-qubit couplings (2005)
We propose an approach suitable for solving NP-complete problems via adiabatic quantum computation with an architecture based on a lattice of interacting spins (qubits) driven by locally adjustable...
Approximating satisfiability transition by suppressing fluctuations (2004)
Knysh, S., Smelyanskiy, V. N., Morris, R. D.
Using methods and ideas from statistical mechanics, we propose a simple method for obtaining rigorous upper bounds for satisfiability transition in random boolean expressions composed of N variables...
Quantum adiabatic optimization and combinatorial landscapes (2004)
Smelyanskiy, V. N., Knysh, S., Morris, R. D.
In this paper we analyze the performance of the Quantum Adiabatic Evolution algorithm on a variant of Satisfiability problem for an ensemble of random graphs parametrized by the ratio of clauses to...