Misplaced Pages

#466533

96-464: A decision problem is a member of BQP if there exists a quantum algorithm (an algorithm that runs on a quantum computer) that solves the decision problem with high probability and is guaranteed to run in polynomial time. A run of the algorithm will correctly solve the decision problem with a probability of at least 2/3. BQP can be viewed as the languages associated with certain bounded-error uniform families of quantum circuits . A language L

192-405: A random oracle answers each query randomly but consistently; the oracle is assumed to be available to all parties including the attacker, as the hash function is. Such a proof shows that unless the attacker solves the hard problem at the heart of the security reduction, they must make use of some interesting property of the hash function to break the protocol; they cannot treat the hash function as

288-488: A Turing machine, includes: In addition to these components, an oracle machine also includes: From time to time, the oracle machine may enter the ASK state. When this happens, the following actions are performed in a single computational step: The effect of changing to the ASK state is thus to receive, in a single step, a solution to the problem instance that is written on the oracle tape. There are many alternative definitions to

384-647: A computer is completely hypothetical and would not be a standard quantum computer, or even possible under the standard theory of quantum mechanics.) Such a hypothetical computer could implement a search of an N-item database in at most O ( N 3 ) {\displaystyle O({\sqrt[{3}]{N}})} steps. This is slightly faster than the O ( N ) {\displaystyle O({\sqrt {N}})} steps taken by Grover's algorithm. However, neither search method would allow either model of quantum computer to solve NP-complete problems in polynomial time. Quantum counting solves

480-482: A few hundred qubits. Quantum computers can also efficiently simulate topological quantum field theories. In addition to its intrinsic interest, this result has led to efficient quantum algorithms for estimating quantum topological invariants such as Jones and HOMFLY polynomials , and the Turaev-Viro invariant of three-dimensional manifolds. In 2009, Aram Harrow , Avinatan Hassidim, and Seth Lloyd , formulated

576-633: A generalization of the search problem. It solves the problem of counting the number of marked entries in an unordered list, instead of just detecting whether one exists. Specifically, it counts the number of marked entries in an N {\displaystyle N} -element list with an error of at most ε {\displaystyle \varepsilon } by making only Θ ( ε − 1 N / k ) {\displaystyle \Theta \left(\varepsilon ^{-1}{\sqrt {N/k}}\right)} queries, where k {\displaystyle k}

672-413: A hierarchy of machines, each with a more powerful halting oracle and an even harder halting problem. This hierarchy of machines can be used to define the arithmetical hierarchy . In cryptography , oracles are used to make arguments for the security of cryptographic protocols where a hash function is used. A security reduction for the protocol is given in the case where, instead of a hash function,

768-705: A history ( u 0 → ⋯ → u m ) {\displaystyle (u_{0}\rightarrow \cdots \rightarrow u_{m})} . The transition amplitude of the history is computable in polynomial time. Each gate g j {\displaystyle g_{j}} can be decomposed into g j = I ⊗ g ~ j {\displaystyle g_{j}=I\otimes {\tilde {g}}_{j}} for some unitary operator g ~ j {\displaystyle {\tilde {g}}_{j}} acting on two qubits, which without loss of generality can be taken to be

864-568: A matrix in C 2 n × 2 n {\displaystyle \mathbb {C} ^{2^{n}\times 2^{n}}} . Hence, the final state | ψ m ⟩ {\displaystyle |\psi _{m}\rangle } can be computed in O ( m ⋅ 2 2 n ) {\displaystyle O(m\cdot 2^{2n})} time, and therefore all together, we have an 2 O ( n ) {\displaystyle 2^{O(n)}} time algorithm for calculating

960-425: A molecule. It is based on classical methods for solving energies and two-electron reduced density matrices directly from the anti-Hermitian contracted Schrödinger equation. Oracle machine In complexity theory and computability theory , an oracle machine is an abstract machine used to study decision problems . It can be visualized as a Turing machine with a black box , called an oracle , which

1056-527: A paper which showed that, relative to an oracle , BQP was not contained in PH . It can be proven that there exists an oracle A such that B Q P A ⊈ P H A {\displaystyle {\mathsf {BQP}}^{\mathrm {A} }\nsubseteq {\mathsf {PH}}^{\mathrm {A} }} . In an extremely informal sense, this can be thought of as giving PH and BQP an identical, but additional, capability and verifying that BQP with

SECTION 10

#1732873244467

1152-403: A polynomial number of quantum gates . The Deutsch–Jozsa algorithm solves a black-box problem that requires exponentially many queries to the black box for any deterministic classical computer, but can be done with a single query by a quantum computer. However, when comparing bounded-error classical and quantum algorithms, there is no speedup, since a classical probabilistic algorithm can solve

1248-411: A polynomial sized quantum circuit on n qubits and m gates, where m is polynomial in n. Let | ψ 0 ⟩ = | 0 ⟩ ⊗ n {\displaystyle |\psi _{0}\rangle =|0\rangle ^{\otimes n}} and | ψ i ⟩ {\displaystyle |\psi _{i}\rangle } be the state after

1344-418: A quantum algorithm for solving linear systems . The algorithm estimates the result of a scalar measurement on the solution vector to a given linear system of equations. Provided that the linear system is sparse and has a low condition number κ {\displaystyle \kappa } , and that the user is interested in the result of a scalar measurement on the solution vector (instead of

1440-435: A quantum algorithm, however, it can be solved in Θ ( N 1 / 2 ) {\displaystyle \Theta (N^{1/2})} queries. No better quantum algorithm for this case was known until one was found for the unconventional Hamiltonian oracle model. The same result for the standard setting soon followed. Fast quantum algorithms for more complicated formulas are also known. The problem

1536-413: A quantum circuit C , which consists of t gates, g 1 , g 2 , ⋯ , g m {\displaystyle g_{1},g_{2},\cdots ,g_{m}} , where each g j {\displaystyle g_{j}} comes from a universal gate set and acts on at most two qubits. To understand what the sum of histories is, we visualize the evolution of

1632-462: A quantum circuit. It is conjectured that BQP solves hard problems outside of P, specifically, problems in NP. The claim is indefinite because we don't know if P=NP, so we don't know if those problems are actually in P. Below are some evidence of the conjecture: Quantum algorithm In quantum computing , a quantum algorithm is an algorithm that runs on a realistic model of quantum computation ,

1728-467: A quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement . Problems that are undecidable using classical computers remain undecidable using quantum computers. What makes quantum algorithms interesting is that they might be able to solve some problems faster than classical algorithms because

1824-482: A quantum computer. The optimal algorithm was put forth by Andris Ambainis , and Yaoyun Shi first proved a tight lower bound when the size of the range is sufficiently large. Ambainis and Kutin independently (and via different proofs) extended that work to obtain the lower bound for all functions. The triangle-finding problem is the problem of determining whether a given graph contains a triangle (a clique of size 3). The best-known lower bound for quantum algorithms

1920-413: A quantum state given a quantum circuit as a tree. The root is the input | 0 ⟩ ⊗ n {\displaystyle |0\rangle ^{\otimes n}} , and each node in the tree has 2 n {\displaystyle 2^{n}} children, each representing a state in C n {\displaystyle \mathbb {C} ^{n}} . The weight on

2016-440: A sequence of CNOT gates to flip the qubits. Then we can combine two circuits to get C ′ = Q n C x {\displaystyle C'=Q_{n}C_{x}} , and now C ′ | 0 ⟩ ⊗ n = Q n | x ⟩ {\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle } . And finally, necessarily

SECTION 20

#1732873244467

2112-485: A set of languages B (or a complexity class B), by using the following definition: When a language L is complete for some class B, then A =A provided that machines in A can execute reductions used in the completeness definition of class B. In particular, since SAT is NP-complete with respect to polynomial time reductions, P =P . However, if A = DLOGTIME , then A may not equal A . (The definition of A B {\displaystyle A^{B}} given above

2208-715: A state | x ⟩ {\displaystyle |x\rangle } of n {\displaystyle n} qubits, if x ∈ L , P r ( Q n ( | x ⟩ ) = 1 ) ≥ 2 / 3 {\displaystyle x\in L,Pr(Q_{n}(|x\rangle )=1)\geq 2/3} ; else if x ∉ L , P r ( Q n ( | x ⟩ ) = 0 ) ≥ 2 / 3 {\displaystyle x\notin L,Pr(Q_{n}(|x\rangle )=0)\geq 2/3} . Fix an input | x ⟩ {\displaystyle |x\rangle } of n qubits, and

2304-499: A suitable quantum computable linear optical network and that sampling of the output probability distribution would be demonstrably superior using quantum algorithms. In 2015, investigation predicted the sampling problem had similar complexity for inputs other than Fock-state photons and identified a transition in computational complexity from classically simulable to just as hard as the Boson Sampling Problem, depending on

2400-469: A tree edge from a node in j -th level representing a state | x ⟩ {\displaystyle |x\rangle } to a node in j + 1 {\displaystyle j+1} -th level representing a state | y ⟩ {\displaystyle |y\rangle } is ⟨ y | g j + 1 | x ⟩ {\displaystyle \langle y|g_{j+1}|x\rangle } ,

2496-423: Is Ω ( N ) {\displaystyle \Omega (N)} , but the best algorithm known requires O( N ) queries, an improvement over the previous best O( N ) queries. A formula is a tree with a gate at each internal node and an input bit at each leaf node. The problem is to evaluate the formula, which is the output of the root node, given oracle access to the input. A well studied formula

2592-495: Is a technique that allows the amplification of a chosen subspace of a quantum state. Applications of amplitude amplification usually lead to quadratic speedups over the corresponding classical algorithms. It can be considered as a generalization of Grover's algorithm. Grover's algorithm searches an unstructured database (or an unordered list) with N entries for a marked entry, using only O ( N ) {\displaystyle O({\sqrt {N}})} queries instead of

2688-426: Is a versatile tool. The Boson Sampling Problem in an experimental configuration assumes an input of bosons (e.g., photons) of moderate number that are randomly scattered into a large number of output modes, constrained by a defined unitarity . When individual photons are used, the problem is isomorphic to a multi-photon quantum walk. The problem is then to produce a fair sample of the probability distribution of

2784-450: Is able to solve certain problems in a single operation. The problem can be of any complexity class . Even undecidable problems , such as the halting problem , can be used. An oracle machine can be conceived as a Turing machine connected to an oracle . The oracle, in this context, is an entity capable of solving some problem, which for example may be a decision problem or a function problem . The problem does not have to be computable;

2880-458: Is also one of the few quantum algorithms that solves a non–black-box problem in polynomial time, where the best known classical algorithms run in super-polynomial time. The abelian hidden subgroup problem is a generalization of many problems that can be solved by a quantum computer, such as Simon's problem, solving Pell's equation , testing the principal ideal of a ring R and factoring . There are efficient quantum algorithms known for

2976-560: Is considered unlikely. However, quantum computers can estimate Gauss sums to polynomial precision in polynomial time. Consider an oracle consisting of n random Boolean functions mapping n -bit strings to a Boolean value, with the goal of finding n n -bit strings z 1 ,..., z n such that for the Hadamard-Fourier transform, at least 3/4 of the strings satisfy and at least 1/4 satisfy This can be done in bounded-error quantum polynomial time (BQP). Amplitude amplification

BQP - Misplaced Pages Continue

3072-596: Is in BQP if and only if there exists a polynomial-time uniform family of quantum circuits { Q n : n ∈ N } {\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}} , such that Alternatively, one can define BQP in terms of quantum Turing machines . A language L is in BQP if and only if there exists a polynomial quantum Turing machine that accepts L with an error probability of at most 1/3 for all instances. Similarly to other "bounded error" probabilistic classes,

3168-480: Is in EXP since APPROX-QCIRCUIT-PROB is BQP-complete. Claim  —  APPROX-QCIRCUIT-PROB ∈ E X P {\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}} The idea is simple. Since we have exponential power, given a quantum circuit C , we can use classical computer to stimulate each gate in C to get the final state. More formally, let C be

3264-494: Is not completely standard. In some contexts, such as the proof of the time and space hierarchy theorems , it is more useful to assume that the abstract machine defining class A {\displaystyle A} only has access to a single oracle for one language. In this context, A B {\displaystyle A^{B}} is not defined if the complexity class B {\displaystyle B} does not have any complete problems with respect to

3360-437: Is only weak evidence that P≠NP, since a statement may be true for a random oracle but false for ordinary Turing machines; for example, IP ≠PSPACE for a random oracle A but IP = PSPACE . A machine with an oracle for the halting problem can determine whether particular Turing machines will halt on particular inputs, but it cannot determine, in general, whether machines equivalent to itself will halt. This creates

3456-438: Is polynomial in n , the transition amplitude of the history can be computed in polynomial time. Claim  —  Let C | 0 ⟩ ⊗ n = ∑ x ∈ { 0 , 1 } n α x | x ⟩ {\displaystyle C|0\rangle ^{\otimes n}=\sum _{x\in \{0,1\}^{n}}\alpha _{x}|x\rangle } be

3552-504: Is suspected and not verified because there is no proof that P ≠ NP ), this illustrates the potential power of quantum computing in relation to classical computing. Adding postselection to BQP results in the complexity class PostBQP which is equal to PP . Promise-BQP is the class of promise problems that can be solved by a uniform family of quantum circuits (i.e., within BQP). Completeness proofs focus on this version of BQP. Similar to

3648-409: Is the balanced binary tree with only NAND gates. This type of formula requires Θ ( N c ) {\displaystyle \Theta (N^{c})} queries using randomness, where c = log 2 ⁡ ( 1 + 33 ) / 4 ≈ 0.754 {\displaystyle c=\log _{2}(1+{\sqrt {33}})/4\approx 0.754} . With

3744-437: Is the length of input. BQP is defined for quantum computers; the corresponding complexity class for classical computers (or more formally for probabilistic Turing machines ) is BPP . Just like P and BPP , BQP is low for itself, which means BQP = BQP . Informally, this is true because polynomial time algorithms are closed under composition. If a polynomial time algorithm calls polynomial time algorithms as subroutines,

3840-425: Is the number of marked elements in the list. More precisely, the algorithm outputs an estimate k ′ {\displaystyle k'} for k {\displaystyle k} , the number of marked entries, with accuracy | k − k ′ | ≤ ε k {\displaystyle |k-k'|\leq \varepsilon k} . A quantum walk

3936-432: Is the quantum analogue of a classical random walk . A classical random walk can be described by a probability distribution over some states, while a quantum walk can be described by a quantum superposition over states. Quantum walks are known to give exponential speedups for some black-box problems. They also provide polynomial speedups for many problems. A framework for the creation of quantum walk algorithms exists and

BQP - Misplaced Pages Continue

4032-401: Is the quantum analogue to the classical complexity class BPP . A problem is BQP -complete if it is in BQP and any problem in BQP can be reduced to it in polynomial time . Informally, the class of BQP -complete problems are those that are as hard as the hardest problems in BQP and are themselves efficiently solvable by a quantum computer (with bounded error). Witten had shown that

4128-774: Is to determine if a black-box group , given by k generators, is commutative . A black-box group is a group with an oracle function, which must be used to perform the group operations (multiplication, inversion, and comparison with identity). The interest in this context lies in the query complexity, which is the number of oracle calls needed to solve the problem. The deterministic and randomized query complexities are Θ ( k 2 ) {\displaystyle \Theta (k^{2})} and Θ ( k ) {\displaystyle \Theta (k)} , respectively. A quantum algorithm requires Ω ( k 2 / 3 ) {\displaystyle \Omega (k^{2/3})} queries, while

4224-477: Is used to determine the eigenphase of an eigenvector of a unitary gate, given a quantum state proportional to the eigenvector and access to the gate. The algorithm is frequently used as a subroutine in other algorithms. Shor's algorithm solves the discrete logarithm problem and the integer factorization problem in polynomial time, whereas the best known classical algorithms take super-polynomial time. These problems are not known to be in P or NP-complete . It

4320-486: The O ( N ) {\displaystyle O({N})} queries required classically. Classically, O ( N ) {\displaystyle O({N})} queries are required even allowing bounded-error probabilistic algorithms. Theorists have considered a hypothetical generalization of a standard quantum computer that could access the histories of the hidden variables in Bohmian mechanics . (Such

4416-741: The Chern-Simons topological quantum field theory (TQFT) can be solved in terms of Jones polynomials . A quantum computer can simulate a TQFT, and thereby approximate the Jones polynomial, which as far as we know, is hard to compute classically in the worst-case scenario. The idea that quantum computers might be more powerful than classical computers originated in Richard Feynman's observation that classical computers seem to require exponential time to simulate many-particle quantum systems, yet quantum many-body systems are able to "solve themselves." Since then,

4512-477: The Hamiltonian oracle model . Quantum algorithms can be categorized by the main techniques involved in the algorithm. Some commonly used techniques/ideas in quantum algorithms include phase kick-back , phase estimation , the quantum Fourier transform , quantum walks , amplitude amplification and topological quantum field theory . Quantum algorithms may also be grouped by the type of problem solved; see, e.g.,

4608-414: The dihedral group , which would solve certain lattice problems. A Gauss sum is a type of exponential sum . The best known classical algorithm for estimating these sums takes exponential time. Since the discrete logarithm problem reduces to Gauss sum estimation, an efficient classical algorithm for estimating Gauss sums would imply an efficient classical algorithm for computing discrete logarithms, which

4704-549: The general number field sieve . Grover's algorithm runs quadratically faster than the best possible classical algorithm for the same task, a linear search . Quantum algorithms are usually described, in the commonly used circuit model of quantum computation, by a quantum circuit that acts on some input qubits and terminates with a measurement . A quantum circuit consists of simple quantum gates , each of which acts on some finite number of qubits. Quantum algorithms may also be stated in other models of quantum computation, such as

4800-492: The i -th gate in the circuit is applied to | ψ i − 1 ⟩ {\displaystyle |\psi _{i-1}\rangle } . Each state | ψ i ⟩ {\displaystyle |\psi _{i}\rangle } can be represented in a classical computer as a unit vector in C 2 n {\displaystyle \mathbb {C} ^{2^{n}}} . Furthermore, each gate can be represented by

4896-501: The Abelian hidden subgroup problem. The more general hidden subgroup problem, where the group isn't necessarily abelian, is a generalization of the previously mentioned problems, as well as graph isomorphism and certain lattice problems . Efficient quantum algorithms are known for certain non-abelian groups. However, no efficient algorithms are known for the symmetric group , which would give an efficient algorithm for graph isomorphism and

SECTION 50

#1732873244467

4992-665: The above two cases. We can solve any problem in BQP with this oracle, by setting α = 2 / 3 , β = 1 / 3 {\displaystyle \alpha =2/3,\beta =1/3} . For any L ∈ B Q P {\displaystyle L\in {\mathsf {BQP}}} , there exists family of quantum circuits { Q n : n ∈ N } {\displaystyle \{Q_{n}\colon n\in \mathbb {N} \}} such that for all n ∈ N {\displaystyle n\in \mathbb {N} } ,

5088-401: The amplitude of | y ⟩ {\displaystyle |y\rangle } after applying g j + 1 {\displaystyle g_{j+1}} on | x ⟩ {\displaystyle |x\rangle } . The transition amplitude of a root-to-leaf path is the product of all the weights on the edges along the path. To get the probability of

5184-399: The best-known classical algorithm uses O ( k 2 / 3 log ⁡ k ) {\displaystyle O(k^{2/3}\log k)} queries. The complexity class BQP (bounded-error quantum polynomial time) is the set of decision problems solvable by a quantum computer in polynomial time with error probability of at most 1/3 for all instances. It

5280-437: The case where an oracle is chosen randomly from among all possible oracles (an infinite set). It has been shown in this case, that with probability 1, P ≠NP . When a question is true for almost all oracles, it is said to be true for a random oracle . This choice of terminology is justified by the fact that random oracles support a statement with probability 0 or 1 only. (This follows from Kolmogorov's zero–one law .) This

5376-452: The choice of 1/3 in the definition is arbitrary. We can run the algorithm a constant number of times and take a majority vote to achieve any desired probability of correctness less than 1, using the Chernoff bound . The complexity class is unchanged by allowing error as high as 1/2 − n on the one hand, or requiring error as small as 2 on the other hand, where c is any positive constant, and n

5472-510: The corresponding quantum circuit Q n {\displaystyle Q_{n}} . We can first construct a circuit C x {\displaystyle C_{x}} such that C x | 0 ⟩ ⊗ n = | x ⟩ {\displaystyle C_{x}|0\rangle ^{\otimes n}=|x\rangle } . This can be done easily by hardwiring | x ⟩ {\displaystyle |x\rangle } and apply

5568-737: The edge ( | u ⟩ , | v ⟩ ) {\displaystyle (|u\rangle ,|v\rangle )} in the j -th level of the sum over histories tree be α j ( u → v ) = ⟨ v | g j | u ⟩ {\displaystyle \alpha _{j}(u\rightarrow v)=\langle v|g_{j}|u\rangle } . For any history h = ( u 0 → u 1 → ⋯ → u m − 1 → u m ) {\displaystyle h=(u_{0}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m})} ,

5664-531: The energy expectation value of an ansatz state to find the ground state of a Hermitian operator, such as a molecule's Hamiltonian. It can also be extended to find excited energies of molecular Hamiltonians. The contracted quantum eigensolver (CQE) algorithm minimizes the residual of a contraction (or projection) of the Schrödinger equation onto the space of two (or more) electrons to find the ground- or excited-state energy and two-electron reduced density matrix of

5760-705: The equation. Then each term corresponds to a α h {\displaystyle \alpha _{h}} , where h = ( | 0 ⟩ ⊗ n → u 1 → ⋯ → u t − 1 → | x ⟩ ) {\displaystyle h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )} Claim  —  APPROX-QCIRCUIT-PROB ∈ P S P A C E {\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {PSPACE}}} Notice in

5856-491: The final state being | ψ ⟩ {\displaystyle |\psi \rangle } , we sum up the amplitudes of all root-to-leave paths that ends at a node representing | ψ ⟩ {\displaystyle |\psi \rangle } . More formally, for the quantum circuit C , its sum over histories tree is a tree of depth m , with one level for each gate g i {\displaystyle g_{i}} in addition to

SECTION 60

#1732873244467

5952-1693: The final state of the quantum circuit. For some x ∈ { 0 , 1 } n {\displaystyle x\in \{0,1\}^{n}} , the amplitude α x {\displaystyle \alpha _{x}} can be computed by α x = ∑ h = ( | 0 ⟩ ⊗ n → u 1 → ⋯ → u t − 1 → | x ⟩ ) α h {\displaystyle \alpha _{x}=\sum _{h=(|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{t-1}\rightarrow |x\rangle )}\alpha _{h}} . We have α x = ⟨ x | C | 0 ⟩ ⊗ n = ⟨ x | g t g t − 1 ⋯ g 1 | C | 0 ⟩ ⊗ n {\displaystyle \alpha _{x}=\langle x|C|0\rangle ^{\otimes n}=\langle x|g_{t}g_{t-1}\cdots g_{1}|C|0\rangle ^{\otimes n}} . The result comes directly by inserting I = ∑ x ∈ { 0 , 1 } n | x ⟩ ⟨ x | {\displaystyle I=\sum _{x\in \{0,1\}^{n}}|x\rangle \langle x|} between g 1 , g 2 {\displaystyle g_{1},g_{2}} , and g 2 , g 3 {\displaystyle g_{2},g_{3}} , and so on, and then expand out

6048-409: The final state, and thus the probability that the first qubit is measured to be one. This implies that APPROX-QCIRCUIT-PROB ∈ E X P {\displaystyle {\text{APPROX-QCIRCUIT-PROB}}\in {\mathsf {EXP}}} . Note that this algorithm also requires 2 O ( n ) {\displaystyle 2^{O(n)}} space to store the vectors and

6144-435: The first case (acceptance), or the second case (rejection), so L ∈ B Q P {\displaystyle L\in {\mathsf {BQP}}} reduces to APPROX-QCIRCUIT-PROB. We begin with an easier containment. To show that B Q P ⊆ E X P {\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}} , it suffices to show that APPROX-QCIRCUIT-PROB

6240-655: The first two. Hence, ⟨ v | g j | u ⟩ = ⟨ v 1 , v 2 | g ~ j | u 1 , u 2 ⟩ ⟨ v 3 , ⋯ , v n | u 3 , ⋯ , u n ⟩ {\displaystyle \langle v|g_{j}|u\rangle =\langle v_{1},v_{2}|{\tilde {g}}_{j}|u_{1},u_{2}\rangle \langle v_{3},\cdots ,v_{n}|u_{3},\cdots ,u_{n}\rangle } which can be computed in polynomial time in n . Since m

6336-590: The following two cases: Here, there is a promise on the inputs as the problem does not specify the behavior if an instance is not covered by these two cases. Claim. Any BQP problem reduces to APPROX-QCIRCUIT-PROB. Proof. Suppose we have an algorithm A that solves APPROX-QCIRCUIT-PROB, i.e., given a quantum circuit C acting on n qubits, and two numbers α , β ∈ [ 0 , 1 ] , α > β {\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta } , A distinguishes between

6432-505: The ground-state eigenvector and eigenvalue of a Hermitian operator. The quantum approximate optimization algorithm takes inspiration from quantum annealing, performing a discretized approximation of quantum annealing using a quantum circuit. It can be used to solve problems in graph theory. The algorithm makes use of classical optimization of quantum operations to maximize an "objective function." The variational quantum eigensolver (VQE) algorithm applies classical optimization to minimize

6528-418: The histories in addition to some workspace variables. Therefore, in polynomial space, we may compute ∑ x | α x | 2 {\displaystyle \sum _{x}|\alpha _{x}|^{2}} over all x with the first qubit being 1 , which is the probability that the first qubit is measured to be 1 by the end of the circuit. Notice that compared with

6624-406: The idea that quantum computers can simulate quantum physical processes exponentially faster than classical computers has been greatly fleshed out and elaborated. Efficient (i.e., polynomial-time) quantum algorithms have been developed for simulating both Bosonic and Fermionic systems, as well as the simulation of chemical reactions beyond the capabilities of current classical supercomputers using only

6720-462: The matrices. We will show in the following section that we can improve upon the space complexity. Sum of histories is a technique introduced by physicist Richard Feynman for path integral formulation . APPROX-QCIRCUIT-PROB can be formulated in the sum of histories technique to show that B Q P ⊆ P S P A C E {\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PSPACE}}} . Consider

6816-468: The most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) 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

6912-586: The notion of NP-completeness and other complete problems, we can define a complete problem as a problem that is in Promise-BQP and that every other problem in Promise-BQP reduces to it in polynomial time. The APPROX-QCIRCUIT-PROB problem is complete for efficient quantum computation, and the version presented below is complete for the Promise-BQP complexity class (and not for the total BQP complexity class, for which no complete problems are known). APPROX-QCIRCUIT-PROB's completeness makes it useful for proofs showing

7008-481: The one by van Melkebeek, using an oracle tape which may have its own alphabet, is required in general. The complexity class of decision problems solvable by an algorithm in class A with an oracle for a language L is called A . For example, P is the class of problems solvable in polynomial time by a deterministic Turing machine with an oracle for the Boolean satisfiability problem . The notation A can be extended to

7104-455: The one presented above. Many of these are specialized for the case where the oracle solves a decision problem. In this case: These definitions are equivalent from the point of view of Turing computability: a function is oracle-computable from a given oracle under all of these definitions if it is oracle-computable under any of them. The definitions are not equivalent, however, from the point of view of computational complexity. A definition such as

7200-464: The oracle (BQP) can do things PH cannot. While an oracle separation has been proven, the fact that BQP is not contained in PH has not been proven. An oracle separation does not prove whether or not complexity classes are the same. The oracle separation gives intuition that BQP may not be contained in PH. It has been suspected for many years that Fourier Sampling is a problem that exists within BQP, but not within

7296-402: The oracle is not assumed to be a Turing machine or computer program. The oracle is simply a " black box " that is able to produce a solution for any instance of a given computational problem: An oracle machine can perform all of the usual operations of a Turing machine, and can also query the oracle to obtain a solution to any instance of the computational problem for that oracle. For example, if

7392-423: The output that depends on the input arrangement of bosons and the unitarity. Solving this problem with a classical computer algorithm requires computing the permanent of the unitary transform matrix, which may take a prohibitively long time or be outright impossible. In 2014, it was proposed that existing technology and standard probabilistic methods of generating single-photon states could be used as an input into

7488-456: The output. This will be our circuit C , and we decide the membership of x ∈ L {\displaystyle x\in L} by running A ( C ) {\displaystyle A(C)} with α = 2 / 3 , β = 1 / 3 {\displaystyle \alpha =2/3,\beta =1/3} . By definition of BQP, we will either fall into

7584-436: The polynomial hierarchy. Recent conjectures have provided evidence that a similar problem, Fourier Checking, also exists in the class BQP without being contained in the polynomial hierarchy . This conjecture is especially notable because it suggests that problems existing in BQP could be classified as harder than NP-Complete problems. Paired with the fact that many practical BQP problems are suspected to exist outside of P (it

7680-402: The problem is a decision problem for a set A of natural numbers, the oracle machine supplies the oracle with a natural number, and the oracle responds with "yes" or "no" stating whether that number is an element of A . There are many equivalent definitions of oracle Turing machines, as discussed below. The one presented here is from van Melkebeek (2003 , p. 43). An oracle machine, like

7776-516: The problem of ⁠ P   = ?   P S P A C E {\displaystyle {\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}} ⁠ has not yet been solved, the proof of inequality between BQP and classes mentioned above is supposed to be difficult. The relation between BQP and NP is not known. In May 2018, computer scientists Ran Raz of Princeton University and Avishay Tal of Stanford University published

7872-410: The problem with a constant number of queries with small probability of error. The algorithm determines whether a function f is either constant (0 on all inputs or 1 on all inputs) or balanced (returns 1 for half of the input domain and 0 for the other half). The Bernstein–Vazirani algorithm is the first quantum algorithm that solves a problem more efficiently than the best known classical algorithm. It

7968-437: The quantum superposition and quantum entanglement that quantum algorithms exploit generally cannot be efficiently simulated on classical computers (see Quantum supremacy ). The best-known algorithms are Shor's algorithm for factoring and Grover's algorithm for searching an unstructured database or an unordered list. Shor's algorithm runs much (almost exponentially) faster than the best-known classical algorithm for factoring,

8064-415: The reductions available to A {\displaystyle A} .) It is understood that NP ⊆ P , but the question of whether NP , P , NP, and P are equal remains tentative at best. It is believed they are different, and this leads to the definition of the polynomial hierarchy . Oracle machines are useful for investigating the relationship between complexity classes P and NP , by considering

8160-451: The relationship between P and NP for an oracle A. In particular, it has been shown there exist languages A and B such that P =NP and P ≠NP . The fact the P = NP question relativizes both ways is taken as evidence that answering this question is difficult, because a proof technique that relativizes (i.e., unaffected by the addition of an oracle) will not answer the P = NP question. Most proof techniques relativize. One may consider

8256-445: The relationships between other complexity classes and BQP. Given a description of a quantum circuit C acting on n qubits with m gates, where m is a polynomial in n and each gate acts on one or two qubits, and two numbers α , β ∈ [ 0 , 1 ] , α > β {\displaystyle \alpha ,\beta \in [0,1],\alpha >\beta } , distinguish between

8352-462: The resulting algorithm is still polynomial time. BQP contains P and BPP and is contained in AWPP , 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 possible difference in power between these similar classes. The known relationships with classic complexity classes are: As

8448-480: The results of Q n {\displaystyle Q_{n}} is obtained by measuring several qubits and apply some (classical) logic gates to them. We can always defer the measurement and reroute the circuits so that by measuring the first qubit of C ′ | 0 ⟩ ⊗ n = Q n | x ⟩ {\displaystyle C'|0\rangle ^{\otimes n}=Q_{n}|x\rangle } , we get

8544-803: The root, and with branching factor 2 n {\displaystyle 2^{n}} . Define  —  A history is a path in the sum of histories tree. We will denote a history by a sequence ( u 0 = | 0 ⟩ ⊗ n → u 1 → ⋯ → u m − 1 → u m = x ) {\displaystyle (u_{0}=|0\rangle ^{\otimes n}\rightarrow u_{1}\rightarrow \cdots \rightarrow u_{m-1}\rightarrow u_{m}=x)} for some final state x . Define  —  Let u , v ∈ { 0 , 1 } n {\displaystyle u,v\in \{0,1\}^{n}} . Let amplitude of

8640-801: The simulation given for the proof that B Q P ⊆ E X P {\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {EXP}}} , our algorithm here takes far less space but far more time instead. In fact it takes O ( m ⋅ 2 m n ) {\displaystyle O(m\cdot 2^{mn})} time to calculate a single amplitude! A similar sum-over-histories argument can be used to show that B Q P ⊆ P P {\displaystyle {\mathsf {BQP}}\subseteq {\mathsf {PP}}} . We know P ⊆ B Q P {\displaystyle {\mathsf {P}}\subseteq {\mathsf {BQP}}} , since every classical circuit can be simulated by

8736-481: The size of coherent amplitude inputs. The element distinctness problem is the problem of determining whether all the elements of a list are distinct. Classically, Ω ( N ) {\displaystyle \Omega (N)} queries are required for a list of size N {\displaystyle N} ; however, it can be solved in Θ ( N 2 / 3 ) {\displaystyle \Theta (N^{2/3})} queries on

8832-518: The sum over histories algorithm to compute some amplitude α x {\displaystyle \alpha _{x}} , only one history is stored at any point in the computation. Hence, the sum over histories algorithm uses O ( n m ) {\displaystyle O(nm)} space to compute α x {\displaystyle \alpha _{x}} for any x since O ( n m ) {\displaystyle O(nm)} bits are needed to store

8928-426: The survey on quantum algorithms for algebraic problems. The quantum Fourier transform is the quantum analogue of the discrete Fourier transform , and is used in several quantum algorithms. The Hadamard transform is also an example of a quantum Fourier transform over an n-dimensional vector space over the field F 2 . The quantum Fourier transform can be efficiently implemented on a quantum computer using only

9024-609: The transition amplitude of the history is the product α h = α 1 ( | 0 ⟩ ⊗ n → u 1 ) α 2 ( u 1 → u 2 ) ⋯ α m ( u m − 1 → x ) {\displaystyle \alpha _{h}=\alpha _{1}(|0\rangle ^{\otimes n}\rightarrow u_{1})\alpha _{2}(u_{1}\rightarrow u_{2})\cdots \alpha _{m}(u_{m-1}\rightarrow x)} . Claim  —  For

9120-793: The values of the solution vector itself), then the algorithm has a runtime of O ( log ⁡ ( N ) κ 2 ) {\displaystyle O(\log(N)\kappa ^{2})} , where N {\displaystyle N} is the number of variables in the linear system. This offers an exponential speedup over the fastest classical algorithm, which runs in O ( N κ ) {\displaystyle O(N\kappa )} (or O ( N κ ) {\displaystyle O(N{\sqrt {\kappa }})} for positive semidefinite matrices). Hybrid Quantum/Classical Algorithms combine quantum state preparation and measurement with classical optimization. These algorithms generally aim to determine

9216-429: Was designed to create an oracle separation between BQP and BPP . Simon's algorithm solves a black-box problem exponentially faster than any classical algorithm, including bounded-error probabilistic algorithms. This algorithm, which achieves an exponential speedup over all classical algorithms that we consider efficient, was the motivation for Shor's algorithm for factoring. The quantum phase estimation algorithm

#466533