Scaling of running time of quantum adiabatic algorithm for propositional satisfiability

Details Scaling of running time of quantum adiabatic algorithm for propositional satisfiability Scaling of running time of quantum adiabatic algorithm for propositional satisfiability

2005-02-14

arxiv.org/abs/quant-ph/0502077v1

Phys.Rev.A 71, 062305 (2005)

Physics

Quantum Physics

7 pages

Scientific paper

10.1103/PhysRevA.71.062305

We numerically study quantum adiabatic algorithm for the propositional
satisfiability. A new class of previously unknown hard instances is identified
among random problems. We numerically find that the running time for such
instances grows exponentially with their size. Worst case complexity of quantum
adiabatic algorithm therefore seems to be exponential.

Affiliated with

Also associated with

No associations

Rating

Scaling of running time of quantum adiabatic algorithm for propositional satisfiability 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 Scaling of running time of quantum adiabatic algorithm for propositional satisfiability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scaling of running time of quantum adiabatic algorithm for propositional satisfiability will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-413584