*banner
 

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.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

You are not logged in 
©2002-2017 Chess