Jump to content

User:ColeDU/Quantum complexity theory

From Wikipedia, the free encyclopedia
< User:ColeDU
This is an old revision of this page, as edited by ColeDU (talk | contribs) at 00:01, 11 October 2020 (I began a section on simulating quantum circuits and added the fourth source and used it as in text citation for this section.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Background[edit]

See also: Computational complexity and Complexity class

A complexity class is a collection of computational problems that can be solved by a computational model under certain resource constraints. For instance, the complexity class P is defined as the set of problems solvable by a Turing machine in polynomial time. Similarly, quantum complexity classes may be defined using quantum models of computation, such as the quantum circuit model or the equivalent quantum Turing machine. One of the main aims of quantum complexity theory is to find out how these classes relate to classical complexity classes such as P, NP, BPP, and PSPACE.

One of the reasons quantum complexity theory is studied are the implications of quantum computing for the modern Church-Turing thesis. In short the modern Church-Turing thesis states that any computational model can be simulated in polynomial time with a probabilistic Turing machine.[1] However, questions around the Church-Turing thesis arise in the context of quantum computing. It is unclear whether the Church-Turing thesis holds for the quantum computation model. There is much evidence that the thesis does not hold and that it may not be possible for a probabilistic Turing machine to simulate quantum computation models in polynomial time.[1]

While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the fact that .[2]

Quantum query complexity[edit]

In the query complexity model, the input is given as an oracle (black box). The algorithm gets information about the input only by querying the oracle. The algorithm starts in some fixed quantum state and the state evolves as it queries the oracle.

Quantum query complexity is the smallest number of queries to the oracle that are required in order to calculate the function. This makes the quantum query complexity a lower bound on the overall time complexity of a function.

An example depicting the power of quantum computing is Grover's algorithm for searching unstructured databases. The algorithm's quantum query complexity is , a quadratic improvement over the best possible classical query complexity , which is a linear search. While Grover's algorithm is more optimized than the best possible classical algorithm, we know that Grover's algorithm is not one hundred percent optimal.[3]

Simulating Quantum Circuits

There is no known way to efficiently simulate a quantum computational model with a classical computer. This means that a classical computer cannot simulate a quantum computational model in polynomial time. However, a quantum circuit of qubits with quantum gates can be simulated by a classical circuit with classical gates[4]

References

  1. ^ a b Vazirani, Umesh V. (2002). "A survey of quantum complexity theory". Proceedings of Symposia in Applied Mathematics: 193–217. doi:10.1090/psapm/058/1922899. ISSN 2324-7088.
  2. ^ Watrous, John (2008-04-21). "Quantum Computational Complexity". arXiv:0804.3401 [quant-ph].
  3. ^ Ambainis, Andris (October 28, 2005). "Polynomial degree vs. quantum query complexity". Journal of Computer and System Sciences. 72 (2): 220–238. doi:10.1016/j.jcss.2005.06.006.
  4. ^ Cleve, Richard (2000), "An Introduction to Quantum Complexity Theory", Quantum Computation and Quantum Information Theory, WORLD SCIENTIFIC, pp. 103–127, ISBN 978-981-02-4117-9, retrieved October 10, 2020
Retrieved from "https://en.wikipedia.org/w/index.php?title=User:ColeDU/Quantum_complexity_theory&oldid=982887055"