Topological Fault-Tolerance And Cluster State Quantum Computation, Optical Quantum Computation, Separability Of Very Noisy Mixed States, Supercausality And Consciousness, Electrical Conductivity Of Microtubules, Neuronal Microtubules, Dynamical Localizati

Abstract

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Michael Sipser give a quantum algorithm for solving instances of (e) the satisfiability problem, based on (e) adiabatic evolution. The evolution of the quantum state is governed by (e&eb)a time-dependent Hamiltonian that interpolates between (e&eb) an initial Hamiltonian, whose ground state is easy to construct, and a final Hamiltonian, whose ground state encodes (e) the satisfying assignment. To ensure that the system evolves to *(e&eb) the desired final ground state, the evolution time must be (eb) big enough. Time required depends on (=) the minimum energy differences between (e&eb) the two lowest states of the interpolating Hamiltonian. Authors state they are unable to estimate this gap in general. They give some special symmetric cases of (e) the satisfiability problem where (e) the symmetry allows...

The full paper: http://www.iiste.org/PDFshare/APTA-PAGENO-462105-466356.pdf