On the NP in BQP
Milosh Drezgich, Shankar Sastry

Citation
Milosh Drezgich, Shankar Sastry. "On the NP in BQP". Unpublished article, 2010.

Abstract
One of the central questions of the theory of quantum computation is whether the quantum computers are able to solve, in polynomial time, the problems that are classically currently believed intractable, for example, unstructured search and 3SAT. While mostly believed unlikely, almost all current efforts toward the positive result have been utilizing the quantum adiabatic theorem in the design of the potential algorithm. We show that if the process of computation is governed by the system Hamiltonian, design of the prospective algorithm should not rely on the premise of adiabatic or ground state computation. In particular we prove that the prospective algorithm, represented by the dynamic system through the Schroedinger equation, does not fail simply because the system evolution did not satisfy adiabatic condition or drifted away from the ground state. As a corollary we both present the algorithm in O(n^k) for the unique unstructured search and make conjecture on the algorithm for 3SAT.

Electronic downloads

(No downloads are available for this publication.)

Citation formats

• HTML

  Milosh Drezgich, Shankar Sastry. <a
  href="http://chess.eecs.berkeley.edu/pubs/781.html"
  ><i>On the NP in BQP</i></a>,
  Unpublished article,  2010.

• Plain text

  Milosh Drezgich, Shankar Sastry. "On the NP in
  BQP". Unpublished article,  2010.

• BibTeX

  @unpublished{DrezgichSastry10_OnNPInBQP,
      author = {Milosh Drezgich and Shankar Sastry},
      title = {On the NP in BQP},
      year = {2010},
      abstract = {One of the central questions of the theory of
                quantum computation is whether the quantum
                computers are able to solve, in polynomial time,
                the problems that are classically currently
                believed intractable, for example, unstructured
                search and 3SAT. While mostly believed unlikely,
                almost all current efforts toward the positive
                result have been utilizing the quantum adiabatic
                theorem in the design of the potential algorithm.
                We show that if the process of computation is
                governed by the system Hamiltonian, design of the
                prospective algorithm should not rely on the
                premise of adiabatic or ground state computation.
                In particular we prove that the prospective
                algorithm, represented by the dynamic system
                through the Schroedinger equation, does not fail
                simply because the system evolution did not
                satisfy adiabatic condition or drifted away from
                the ground state. As a corollary we both present
                the algorithm in O(n^k) for the unique
                unstructured search and make conjecture on the
                algorithm for 3SAT. },
      URL = {http://chess.eecs.berkeley.edu/pubs/781.html}
  }
  

Posted by Christopher Brooks on 24 Nov 2010.
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.