NationMaster - Encyclopedia: BQP

BQP, in computational complexity theory, stands for "Bounded error, Quantum, Polynomial time". It denotes the class of problems solvable by a quantum computer in polynomial time, with an error probability of at most 1/4 for all instances. Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In computational complexity theory, Polynomial time refers to the computation time of a problem where the time, m(n), is no greater than a polynomial function of the problem size, n. ... Molecule of alanine used in NMR implementation of error correction. ...

In other words, there is an algorithm for a quantum computer that is guaranteed to run in polynomial time. On any given run of the algorithm, it has a probability of at most 1/4 that it will give the wrong answer. That is true, whether the answer is YES or NO. Flowcharts are often used to represent algorithms. ...

The choice of 1/4 in the definition is arbitrary. Changing the constant to any real number k such that 0 < k < 1/2 does not change the set BQP. The idea is that there is a small probability of error, but running the algorithm many times produces an exponentially-small chance that the majority of the runs are wrong. A mathematical constant is a quantity, usually a real number or a complex number, that arises naturally in mathematics and does not change. ... In mathematics, the real numbers are intuitively defined as numbers that are in one-to-one correspondence with the points on an infinite line—the number line. ... In mathematics, a set can be thought of as any well-defined collection of things considered as a whole. ... Probability of error in hypothesis testing In hypothesis testing in statistics, two types of error are distinguished. ... A quantity is said to be subject to exponential decay if it decreases at a rate proportional to its value. ...

The number of qubits in the computer is allowed to be a function of the instance size. For example, algorithms are known for factoring an n-bit integer using just over 2n qubits. A quantum bit, or qubit is a unit of quantum information. ... In mathematics, a function is a relation, such that each element of a set (the domain) is associated with a unique element of another (possibly the same) set (the codomain, not to be confused with the range). ...

Quantum computers have gained widespread interest because some problems of practical interest are known to be in BQP, but suspected to be outside P. Currently, only three such problems are known:

This class is defined for a quantum computer. The corresponding class for an ordinary Turing machine plus a source of randomness is BPP. In mathematics, the integer prime-factorization (also known as prime decomposition) problem is this: given a positive integer, write it as a product of prime numbers. ... Shors algorithm is a quantum algorithm for factoring a number N in O((log N)3) time and O(log N) space, named after Peter Shor. ... In abstract algebra and its applications, the discrete logarithms are defined in group theory in analogy to ordinary logarithms. ... The universal quantum computer or universal quantum Turing machine (UQTM) is a theoretical machine that combines both Church-Turing and quantum principles. ... Artists conception of a universal Turing machine. ... This article is about the complexity class. ...

BQP contains P and BPP and is contained in PP and PSPACE. In fact, BQP is low for PP, meaning that a PP machine achieves no benefit from being able to solve BQP problems instantly, an indication of the vast difference in power between these similar classes. In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... This article is about the complexity class. ... 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. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... In computational complexity theory, it is said that a complexity class B is 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...

Categories: Complexity classes | Quantum information science In computational complexity theory, a complexity class is a set of problems of related complexity. ... This is a list of complexity classes in computational complexity theory. ... In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... In computational complexity theory, NP (Non-deterministic Polynomial time) is the MONKEY ... In the complexity theory, co-NP is the complexity class that contains the complements of decision problems in the complexity class NP. The complement of a decision problem is here defined as the problem with the yes and no answers reversed, or if we define decision problems as sets of... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... In complexity theory, the complexity class Co-NP-complete is the set of problems that are the hardest problems in Co-NP, in the sense that they are the ones most likely not to be in P. If you can find a way to solve a Co-NP-complete problem... In computational complexity theory, NP-hard (Non-deterministic Polynomial-time hard) refers to the class of decision problems that contains all problems H such that for all decision problems L in NP there is a polynomial-time many-one reduction to H. Informally this class can be described as containing... In complexity theory, UP (Unambiguous Non-deterministic Polynomial-time) is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input. ... The title given to this article is incorrect due to technical limitations. ... The title given to this article is incorrect due to technical limitations. ... In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space. ... In complexity theory, the class NC (Nicks Class) is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. ... In complexity theory, the complexity class P-complete is a set of decision problems and is useful in the analysis of which problems can be efficiently solved on parallel computers. ... In complexity theory the class PSPACE, which equals NPSPACE by Savitchs theorem, is the set of decision problems that can be solved by a deterministic or nondeterministic Turing machine using a polynomial amount of memory and unlimited time. ... In complexity theory, PSPACE-complete is a complexity class. ... In computational complexity theory, the complexity class EXPTIME (sometimes called EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. ... In complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in O(2p(n)) space, where p(n) is a polynomial function of n. ... This article is about the complexity class. ... RP or rp may stand for: Received Pronunciation Republic of Poland Republic of the Philippines RP, a complexity class in computational complexity theory rupee Recommended practice Re-Purchase Agreement Role-playing Retinitis pigmentosa Rapid prototyping Rocket Power Rating Pending, a rating by ESRB, that doesnt have an official rating... In complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is the set of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer. ... In computational complexity theory, PCP is the class of decision problems having probabilistically checkable proof systems. ... In computational complexity theory, IP (Interactive Polynomial-time) is a complexity class of problems solvable by a particular kind of interactive proof system. ... In computational complexity theory, the complexity class PH is the union of all complexity classes in the polynomial hierarchy: PH is contained in the complexity classes PPP (the class of problems that are decidable by a polynomial time Turing machine with an access to PP oracle) and PSPACE. PH has...