the discrete logarithm problem are known to be in BQP and are suspected to be outside of P. On the relationship of BQP to NP, little is known beyond the fact that some NP problems that are believed not to be in P are also in BQP (integer factorization and the discrete logarithm problem are both in NP, for example). It is suspected that ; that is, it is believed that there are efficiently checkable problems that are not efficiently solvable by a quantum computer. As a direct consequence of this belief, it is also suspected that BQP is disjoint from the class of NP-complete problems (if an NP-complete problem were in BQP, then it would follow from NP-hardness that all problems in NP are in BQP). The relationship of BQP to the basic classical complexity classes can be summarized as follows: It is also known that BQP is contained in the complexity class (or more precisely in the associated class of decision problems ), which is a subclass of PSPACE. It has been speculated that further advances in physics could lead to even faster computers. For instance, it has been shown that a non-local hidden variable quantum computer based on Bohmian Mechanics could implement a search of an -item database in at most steps, a slight speedup over Grover's algorithm, which runs in steps. Note, however, that neither search method would allow quantum computers to solve NP-complete problems in polynomial time. Theories of quantum gravity, such as M-theory and loop quantum gravity, may allow even faster computers to be built. However, defining computation in these theories is an open problem due to the problem of time; that is, within these physical theories there is currently no obvious way to describe what it means for an observer to submit input to a computer at one point in time and then receive output at a later point in time. See also D-Wave Systems Electronic quantum holography Glossary of quantum computing IARPA List of emerging technologies List of quantum processors Magic state distillation Natural computing Optical computing Quantum bus Quantum cognition Quantum volume Quantum weirdness Rigetti Computing Supercomputer Theoretical computer science Unconventional computing Valleytronics Notes References Further reading Textbooks Academic papers Table 1 lists switching and dephasing times for various systems. External links Stanford Encyclopedia of Philosophy: "Quantum Computing" by Amit Hagar and Michael E. Cuffaro. Quantum computing for the very curious