Quantum complexity theory

Last updated

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes.

Contents

Two important quantum complexity classes are BQP and QMA.

Background

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] [2] 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. It may not be possible for a probabilistic Turing machine to simulate quantum computation models in polynomial time. [1]

Both quantum computational complexity of functions and classical computational complexity of functions are often expressed with asymptotic notation. Some common forms of asymptotic notion of functions are , , and . expresses that something is bounded above by where is a constant such that and is a function of , expresses that something is bounded below by where is a constant such that and is a function of , and expresses both and . [3] These notations also their own names. is called Big O notation, is called Big Omega notation, and is called Big Theta notation.

Overview of complexity classes

Some important complexity classes are P, BPP, BQP, PP, and P-Space. To define these we first define a promise problem. A promise problem is a decision problem which has an input assumed to be selected from the set of all possible input strings. A promise problem is a pair . is the set of yes instances, is the set of no instances, and the intersection of these sets is such that . All of the previous complexity classes contain promise problems. [4]

Complexity ClassCriteria
PPromise problems for which a polynomial time deterministic Turing machine accepts all strings in and rejects all strings in [4]
BPPPromise problems for which a polynomial time Probabilistic Turing machine accepts every string in with a probability of at least , and accepts every string in with a probability of at most [4]
BQPPromise problems such that for functions , there exists a polynomial time generated family of quantum circuits , where is a circuit which accepts qubits and gives an output of one qubit. An element of is accepted by with a probability greater than or equal to . An element of is accepted by with a probability less than or equal to . [4]
PPPromise problems for which a polynomial time Probabilistic Turing machine accepts every string in with a probability greater than , and accepts every string in with a probability of at most [4]
P-SPACEPromise problems for which a deterministic Turing machine, that runs in polynomial space, accepts every string in and rejects all strings in [4]

BQP

BQP algorithm (1 run)
Answer
produced
Correct
answer
YesNo
Yes≥ 2/3≤ 1/3
No≤ 1/3≥ 2/3
The suspected relationship of BQP to other complexity classes. BQP complexity class diagram.svg
The suspected relationship of BQP to other complexity classes.

The class of problems that can be efficiently solved by a quantum computer with bounded error is called BQP ("bounded error, quantum, polynomial time"). More formally, BQP is the class of problems that can be solved by a polynomial-time quantum Turing machine with error probability of at most 1/3.

As a class of probabilistic problems, BQP is the quantum counterpart to BPP ("bounded error, probabilistic, polynomial time"), the class of problems that can be efficiently solved by probabilistic Turing machines with bounded error. [6] It is known that BPPBQP and widely suspected, but not proven, that BQPBPP, which intuitively would mean that quantum computers are more powerful than classical computers in terms of time complexity. [7] BQP is a subset of PP.

The exact relationship of BQP to P, NP, and PSPACE is not known. However, it is known that PBQPPSPACE; that is, the class of problems that can be efficiently solved by quantum computers includes all problems that can be efficiently solved by deterministic classical computers but does not include any problems that cannot be solved by classical computers with polynomial space resources. It is further suspected that BQP is a strict superset of P, meaning there are problems that are efficiently solvable by quantum computers that are not efficiently solvable by deterministic classical computers. For instance, integer factorization and 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 are in BQP (integer factorization and the discrete logarithm problem are both in NP, for example). It is suspected that NPBQP; 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 any NP-complete problem were in BQP, then it follows from NP-hardness that all problems in NP are in BQP). [8]

The relationship of BQP to the essential classical complexity classes can be summarized as:

It is also known that BQP is contained in the complexity class #P (or more precisely in the associated class of decision problems P#P), [8] which is a subset of PSPACE.

Simulation of 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. [3] This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the qubits must be accounted for. Each of the states of the qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a linear combination of its component vectors with coefficients called amplitudes. These amplitudes are complex numbers which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one. [3] The entries of the state vector are these amplitudes. Which entry each of the amplitudes are correspond to the none-zero component of the component vector which they are the coefficients of in the linear combination description. As an equation this is described as or using Dirac notation. The state of the entire qubit system can be described by a single state vector. This state vector describing the entire system is the tensor product of the state vectors describing the individual qubits in the system. The result of the tensor products of the qubits is a single state vector which has dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, amplitudes must be accounted for with a dimensional complex vector which is the state vector for the qubit system. [9] In order to obtain an upper bound for the number of gates required to simulate a quantum circuit we need a sufficient upper bound for the amount data used to specify the information about each of the amplitudes. To do this bits of precision are sufficient for encoding each amplitude. [3] So it takes classical bits to account for the state vector of the qubit system. Next the application of the quantum gates on amplitudes must be accounted for. The quantum gates can be represented as sparse matrices. [3] So to account for the application of each of the quantum gates, the state vector must be multiplied by a sparse matrix for each of the quantum gates. Every time the state vector is multiplied by a sparse matrix, arithmetic operations must be performed. [3] Therefore, there are bit operations for every quantum gate applied to the state vector. So classical gate are needed to simulate qubit circuit with just one quantum gate. Therefore, classical gates are needed to simulate a quantum circuit of qubits with quantum gates. [3] 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 belief that . [4]

Quantum query complexity

One major advantage of using a quantum computational system instead of a classical one, is that a quantum computer may be able to give a polynomial time algorithm for some problem for which no classical polynomial time algorithm exists, but more importantly, a quantum computer may significantly decrease the calculation time for a problem that a classical computer can already solve efficiently. Essentially, a quantum computer may be able to both determine how long it will take to solve a problem, while a classical computer may be unable to do so, and can also greatly improve the computational efficiency associated with the solution to a particular problem. Quantum query complexity refers to how complex, or how many queries to the graph associated with the solution of a particular problem, are required to solve the problem. Before we delve further into query complexity, let us consider some background regarding graphing solutions to particular problems, and the queries associated with these solutions.

Query models of directed graphs

One type of problem that quantum computing can make easier to solve are graph problems. If we are to consider the amount of queries to a graph that are required to solve a given problem, let us first consider the most common types of graphs, called directed graphs, that are associated with this type of computational modelling. In brief, directed graphs are graphs where all edges between vertices are unidirectional. Directed graphs are formally defined as the graph , where N is the set of vertices, or nodes, and E is the set of edges. [10]

Adjacency matrix model

When considering quantum computation of the solution to directed graph problems, there are two important query models to understand. First, there is the adjacency matrix model, where the graph of the solution is given by the adjacency matrix: , with , if and only if . [11]

Adjacency array model

Next, there is the slightly more complicated adjacency array model built on the idea of adjacency lists, where every vertex, , is associated with an array of neighboring vertices such that , for the out-degrees of vertices , where is the minimum value of the upper bound of this model, and returns the "" vertex adjacent to . Additionally, the adjacency array model satisfies the simple graph condition, , meaning that there is only one edge between any pair of vertices, and the number of edges is minimized throughout the entire model (see Spanning tree model for more background). [11]

Quantum query complexity of certain types of graph problems

Both of the above models can be used to determine the query complexity of particular types of graphing problems, including the connectivity, strong connectivity (a directed graph version of the connectivity model), minimum spanning tree, and single source shortest path models of graphs. An important caveat to consider is that the quantum complexity of a particular type of graphing problem can change based on the query model (namely either matrix or array) used to determine the solution. The following table showing the quantum query complexities of these types of graphing problems illustrates this point well.

Quantum query complexity of certain types of graph problems
ProblemMatrix modelArray model
Minimum spanning tree
Connectivity
Strong connectivity,
Single source shortest path, ,

Notice the discrepancy between the quantum query complexities associated with a particular type of problem, depending on which query model was used to determine the complexity. For example, when the matrix model is used, the quantum complexity of the connectivity model in Big O notation is , but when the array model is used, the complexity is . Additionally, for brevity, we use the shorthand in certain cases, where . [11] The important implication here is that the efficiency of the algorithm used to solve a graphing problem is dependent on the type of query model used to model the graph.

Other types of quantum computational queries

In the query complexity model, the input can also be 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.

Similar to the case of graphing problems, the quantum query complexity of a black-box problem 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.

Grover's algorithm

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. Grover's algorithm is asymptotically optimal; in fact, it uses at most a fraction more queries than the best possible algorithm. [12]

Deutsch-Jozsa algorithm

The Deutsch-Jozsa algorithm is a quantum algorithm designed to solve a toy problem with a smaller query complexity than is possible with a classical algorithm. The toy problem asks whether a function is constant or balanced, those being the only two possibilities. [2] The only way to evaluate the function is to consult a black box or oracle. A classical deterministic algorithm will have to check more than half of the possible inputs to be sure of whether or not the function is constant or balanced. With possible inputs, the query complexity of the most efficient classical deterministic algorithm is . [2] The Deutsch-Jozsa algorithm takes advantage of quantum parallelism to check all of the elements of the domain at once and only needs to query the oracle once, making its query complexity . [2] What is quantum computing? Quantum computing is a science that uses quantum physics to process information that is updated according to algorithms that process [logical instances ], and solves all problems of complexity theory through the evolution of quantum states. https://www.linkedin.com/pulse/general-description-infinitesimal-vector-released-photon-eleuch/

See also

Notes

  1. 1 2 Vazirani, Umesh V. (2002). "A survey of quantum complexity theory". Proceedings of Symposia in Applied Mathematics. 58: 193–217. doi:10.1090/psapm/058/1922899. ISBN   9780821820841. ISSN   2324-7088.
  2. 1 2 3 4 Nielsen, Michael A., 1974- (2010). Quantum computation and quantum information. Chuang, Isaac L., 1968- (10th anniversary ed.). Cambridge: Cambridge University Press. ISBN   978-1-107-00217-3. OCLC   665137861.CS1 maint: multiple names: authors list (link)
  3. 1 2 3 4 5 6 7 Cleve, Richard (2000), "An Introduction to Quantum Complexity Theory", Quantum Computation and Quantum Information Theory, WORLD SCIENTIFIC, pp. 103–127, arXiv: quant-ph/9906111 , Bibcode:2000qcqi.book..103C, doi:10.1142/9789810248185_0004, ISBN   978-981-02-4117-9, S2CID   958695 , retrieved October 10, 2020
  4. 1 2 3 4 5 6 7 Watrous, John (2008-04-21). "Quantum Computational Complexity". arXiv: 0804.3401 [quant-ph].
  5. Nielsen, p. 42
  6. Nielsen, Michael; Chuang, Isaac (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. p. 41. ISBN   978-0-521-63503-5. OCLC   174527496.
  7. Nielsen, p. 201
  8. 1 2 Bernstein, Ethan; Vazirani, Umesh (1997). "Quantum Complexity Theory". SIAM Journal on Computing. 26 (5): 1411–1473. CiteSeerX   10.1.1.144.7852 . doi:10.1137/S0097539796300921.
  9. Häner, Thomas; Steiger, Damian S. (2017-11-12). "0.5 petabyte simulation of a 45-qubit quantum circuit". Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. New York, NY, USA: ACM: 1–10. arXiv: 1704.01127 . doi:10.1145/3126908.3126947. ISBN   978-1-4503-5114-0. S2CID   3338733.
  10. Nykamp, D.Q. "Directed Graph Definition".
  11. 1 2 3 Durr, Christoph; Heiligman, Mark; Hoyer, Peter; Mhalla, Mehdi (January 2006). "Quantum query complexity of some graph problems". SIAM Journal on Computing. 35 (6): 1310–1328. arXiv: quant-ph/0401091 . doi:10.1137/050644719. ISSN   0097-5397. S2CID   27736397.
  12. Zalka, Christof (1999-10-01). "Grover's quantum searching algorithm is optimal". Physical Review A. 60 (4): 2746–2751. arXiv: quant-ph/9711070 . Bibcode:1999PhRvA..60.2746Z. doi:10.1103/PhysRevA.60.2746. S2CID   1542077.

Related Research Articles

In computational complexity theory, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded away from 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

In computational complexity theory, bounded-error quantum polynomial time (BQP) is the class of decision problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/3 for all instances. It is the quantum analogue to the complexity class BPP.

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to time and memory requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem.

Computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

Quantum computing is the use of quantum phenomena such as superposition and entanglement to perform computation. Computers that perform quantum computations are known as quantum computers. Quantum computers are believed to be able to solve certain computational problems, such as integer factorization, substantially faster than classical computers. The study of quantum computing is a subfield of quantum information science. Quantum computing is likely to expand in the next few years as the field shifts towards enabling real-world uses in pharmaceutical, data security and other applications.

Time complexity Estimate of time taken for running an algorithm

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to differ by at most a constant factor.

Complexity class Set of problems in computational complexity theory

In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is usually used for those algorithms which seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement. Why we need a such quantum algorithm ! Quantum computing is a science that uses quantum physics to process information that is updated according to quantum algorithm that process [logical instances of quantum states], and solves all problems of complexity theory through the evolution of quantum states. https://www.linkedin.com/pulse/general-description-infinitesimal-vector-released-photon-eleuch/

In computational complexity theory, P, also known as PTIME or DTIME(nO ), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy:

PP (complexity) Class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances

In complexity theory, PP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of less than 1/2 for all instances. The abbreviation PP refers to probabilistic polynomial time. The complexity class was defined by Gill in 1977.

Quantum logic gate Basic circuit in quantum computing

In quantum computing and specifically the quantum circuit model of computation, a quantum logic gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.

In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON, which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same connected component. This problem is also called the undirected reachability problem. It does not matter whether many-one reducibility or Turing reducibility is used. Although originally described in terms of symmetric Turing machines, that equivalent formulation is very complex, and the reducibility definition is what is used in practice.

In computational complexity theory, a language B is said to be low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost. In particular, this means that if B is low for A then B is contained in A. Informally, lowness means that problems in B are not only solvable by machines which can solve problems in A, but are “easy to solve”. An A machine can simulate many oracle queries to B without exceeding its resource bounds.

A quantum Turing machine (QTM) or universal quantum computer is an abstract machine used to model the effects of a quantum computer. It provides a simple model that captures all of the power of quantum computation—that is, any quantum algorithm can be expressed formally as a particular quantum Turing machine. However, the computationally equivalent quantum circuit is a more common model.

In computational complexity theory, PostBQP is a complexity class consisting of all of the computational problems solvable in polynomial time on a quantum Turing machine with postselection and bounded error.

In computational complexity theory, QMA, which stands for Quantum Merlin Arthur, is the quantum analog of the nonprobabilistic complexity class NP or the probabilistic complexity class MA. It is related to BQP in the same way NP is related to P, or MA is related to BPP.

The quantum algorithm for linear systems of equations, designed by Aram Harrow, Avinatan Hassidim, and Seth Lloyd, is a quantum algorithm formulated in 2009 for solving linear systems. The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations.

In quantum computing, quantum supremacy or quantum advantage is the goal of demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time. Conceptually, quantum supremacy involves both the engineering task of building a powerful quantum computer and the computational-complexity-theoretic task of finding a problem that can be solved by that quantum computer and has a superpolynomial speedup over the best known or possible classical algorithm for that task. The term was coined by John Preskill in 2012, but the concept of a quantum computational advantage, specifically for simulating quantum systems, dates back to Yuri Manin's (1980) and Richard Feynman's (1981) proposals of quantum computing. Examples of proposals to demonstrate quantum supremacy include the boson sampling proposal of Aaronson and Arkhipov, D-Wave's specialized frustrated cluster loop problems, and sampling the output of random quantum circuits.

References