Bounds on the quantum satisfibility threshold

Details Bounds on the quantum satisfibility threshold Bounds on the quantum satisfibility threshold

2009-07-07

arxiv.org/abs/0907.1297v2

Physics

Quantum Physics

Scientific paper

Quantum k-SAT is the problem of deciding whether there is a n-qubit state which is perpendicular to a set of vectors, each of which lies in the Hilbert space of k qubits. Equivalently, the problem is to decide whether a particular type of local Hamiltonian has a ground state with zero energy. We consider random quantum k-SAT formulas with n variables and m = \alpha n clauses, and ask at what value of \alpha these formulas cease to be satisfiable. We show that the threshold for random quantum 3-SAT is at most 3.594. For comparison, convincing arguments from statistical physics suggest that the classical 3-SAT threshold is \alpha \approx 4.267. For larger k, we show that the quantum threshold is a constant factor smaller than the classical one. Our bounds work by determining the generic rank of the satisfying subspace for certain gadgets, and then using the technique of differential equations to analyze various algorithms that partition the hypergraph into a collection of these gadgets. Our use of differential equation to establish upper bounds on a satisfiability threshold appears to be novel, and our techniques may apply to various classical problems as well.

Affiliated with

Also associated with

No associations

Rating

Bounds on the quantum satisfibility threshold does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Bounds on the quantum satisfibility threshold, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds on the quantum satisfibility threshold will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-319458