Misplaced Pages

#547452

63-425: The relationship between QMA and BQP is analogous to the relationship between complexity classes NP and P . It is also analogous to the relationship between the probabilistic complexity class MA and BPP . QAM is a related complexity class, in which fictional agents Arthur and Merlin carry out the sequence: Arthur generates a random string, Merlin answers with a quantum certificate and Arthur verifies it as

126-482: 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 the problem of ⁠ P   = ?   P S P A C E {\displaystyle {\mathsf {P}}\ {\stackrel {?}{=}}\ {\mathsf {PSPACE}}} ⁠ has not yet been solved,

189-397: A BQP machine. A language L is in Q M A ( c , s ) {\displaystyle {\mathsf {QMA}}(c,s)} if there exists a polynomial time quantum verifier V and a polynomial ⁠ p ( x ) {\displaystyle p(x)} ⁠ such that: The complexity class Q M A {\displaystyle {\mathsf {QMA}}}

252-889: A classical proof by measuring proofs as soon as they are received. The fact that QMA is contained in PP was shown by Alexei Kitaev and John Watrous . PP is also easily shown to be in PSPACE . It is unknown if any of these inclusions is unconditionally strict, as it is not even known whether P is strictly contained in PSPACE or P = PSPACE. However, the currently best known upper bounds on QMA are where both A 0 P P {\displaystyle {\mathsf {A_{0}PP}}} and P Q M A [ l o g ] {\displaystyle {\mathsf {P^{QMA[log]}}}} are contained in P P {\displaystyle {\mathsf {PP}}} . It

315-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

378-484: A k-local Hamiltonian H {\displaystyle H} , to find the smallest eigenvalue λ {\displaystyle \lambda } of H {\displaystyle H} . λ {\displaystyle \lambda } is also called the ground state energy of the Hamiltonian. The decision version of the k-local Hamiltonian problem is a type of promise problem and

441-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

504-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

567-402: A promise problem, there are two languages, L YES {\displaystyle L_{\text{YES}}} and L NO {\displaystyle L_{\text{NO}}} , which must be disjoint , which means L YES ∩ L NO = ∅ {\displaystyle L_{\text{YES}}\cap L_{\text{NO}}=\varnothing } , such that all

630-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

693-449: 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: Promise problem In computational complexity theory , a promise problem is a generalization of a decision problem where

SECTION 10

#1732802523548

756-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

819-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

882-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

945-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 } ,

1008-455: 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, 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

1071-751: Is defined as, given a k-local Hamiltonian and α , β {\displaystyle \alpha ,\beta } where α > β {\displaystyle \alpha >\beta } , to decide if there exists a quantum eigenstate | ψ ⟩ {\displaystyle |\psi \rangle } of H {\displaystyle H} with associated eigenvalue λ {\displaystyle \lambda } , such that λ ≤ β {\displaystyle \lambda \leq \beta } or if λ ≥ α {\displaystyle \lambda \geq \alpha } . The local Hamiltonian problem

1134-818: Is defined to be equal to Q M A ( 2 / 3 , 1 / 3 ) {\displaystyle {\mathsf {QMA}}({2}/{3},1/3)} . However, the constants are not too important since the class remains unchanged if c and s are set to any constants such that c is greater than s . Moreover, for any polynomials q ( n ) {\displaystyle q(n)} and r ( n ) {\displaystyle r(n)} , we have Since many interesting classes are contained in QMA, such as P, BQP and NP, all problems in those classes are also in QMA. However, there are problems that are in QMA but not known to be in NP or BQP. Some such well known problems are discussed below. A problem

1197-478: Is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt. A decision problem can be associated with a language L ⊆ { 0 , 1 } ∗ {\displaystyle L\subseteq \{0,1\}^{*}} , where the problem is to accept all inputs in L {\displaystyle L} and reject all inputs not in L {\displaystyle L} . For

1260-457: 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, 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

1323-483: 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

SECTION 20

#1732802523548

1386-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

1449-670: Is said to be QMA-hard, analogous to NP-hard , if every problem in QMA can be reduced to it. A problem is said to be QMA- complete if it is QMA-hard and in QMA. A k-local Hamiltonian (quantum mechanics) H {\displaystyle H} is a Hermitian matrix acting on n qubits which can be represented as the sum of m {\displaystyle m} Hamiltonian Terms acting upon at most k {\displaystyle k} qubits each. H = ∑ i = 1 m H i {\displaystyle H=\sum _{i=1}^{m}H_{i}} The general k-local Hamiltonian problem is, given

1512-412: Is similar to QMA, but the proof has to be a classical string. It is not known whether QMA equals QCMA, although QCMA is clearly contained in QMA. QIP(k) , which stands for Quantum Interactive Polynomial time (k messages), is a generalization of QMA where Merlin and Arthur can interact for k rounds. QMA is QIP(1). QIP(2) is known to be in PSPACE. QIP is QIP(k) where k is allowed to be polynomial in

1575-511: 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

1638-419: Is the quantum analogue of MAX-SAT . The k-local Hamiltonian problem is QMA-complete for k ≥ 2. The 2-local Hamiltonian problem restricted to act on a two dimensional grid of qubits , is also QMA-complete. It has been shown that the k-local Hamiltonian problem is still QMA-hard even for Hamiltonians representing a 1-dimensional line of particles with nearest-neighbor interactions with 12 states per particle. If

1701-417: Is the quantum analogue to the complexity class BPP . 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

1764-494: Is unknown whether P Q M A [ l o g ] ⊆ A 0 P P {\displaystyle {\mathsf {P^{QMA[log]}}}\subseteq {\mathsf {A_{0}PP}}} or vice versa. BQP 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

1827-445: Is unlikely that Q M A {\displaystyle {\mathsf {QMA}}} equals P Q M A [ l o g ] {\displaystyle {\mathsf {P^{QMA[log]}}}} , as this would imply Q M A = c o {\displaystyle {\mathsf {QMA}}={\mathsf {co}}} - Q M A {\displaystyle {\mathsf {QMA}}} . It

1890-487: 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 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

1953-762: The Pauli matrices σ z , σ x {\displaystyle \sigma _{z},\sigma _{x}} . Such models are applicable to universal adiabatic quantum computation . k-local Hamiltonians problems are analogous to classical Constraint Satisfaction Problems . The following table illustrates the analogous gadgets between classical CSPs and Hamiltonians. A list of known QMA-complete problems can be found at https://arxiv.org/abs/1212.6312 . QCMA (or MQA ), which stands for Quantum Classical Merlin Arthur (or Merlin Quantum Arthur),

QMA - Misplaced Pages Continue

2016-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

2079-447: The languages associated with certain bounded-error uniform families of quantum circuits . A language L 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

2142-668: 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} } ,

2205-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

2268-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

2331-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})} ,

2394-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

2457-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

2520-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

2583-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

QMA - Misplaced Pages Continue

2646-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

2709-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

2772-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

2835-444: The graph has a path of length 10. The yes instances are directed acyclic graphs with a path of length 10, whereas the no instances are directed acyclic graphs with no path of length 10. The promise is the set of directed acyclic graphs. In this example, the promise is easy to check. In particular, it is very easy to check if a given graph is cyclic. However, the promised property could be difficult to evaluate. For instance, consider

2898-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

2961-433: The input is promised to belong to a particular subset of all possible inputs. Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes ) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no . If such an input

3024-402: The inputs in L YES {\displaystyle L_{\text{YES}}} are to be accepted and all inputs in L NO {\displaystyle L_{\text{NO}}} are to be rejected. The set L YES ∪ L NO {\displaystyle L_{\text{YES}}\cup L_{\text{NO}}} is called the promise . There are no requirements on

3087-463: 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

3150-592: 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

3213-415: The number of qubits. It is known that QIP(3) = QIP. It is also known that QIP = IP = PSPACE . QMA is related to other known complexity classes by the following relations: The first inclusion follows from the definition of NP . The next two inclusions follow from the fact that the verifier is being made more powerful in each case. QCMA is contained in QMA since the verifier can force the prover to send

SECTION 50

#1732802523548

3276-469: 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

3339-400: The output if the input does not belong to the promise. If the promise equals { 0 , 1 } ∗ {\displaystyle \{0,1\}^{*}} , then this is also a decision problem, and the promise is said to be trivial. Many natural problems are actually promise problems. For instance, consider the following problem: Given a directed acyclic graph , determine if

3402-459: 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

3465-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

3528-800: 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 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

3591-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

3654-482: 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

3717-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

3780-802: 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

3843-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

SECTION 60

#1732802523548

3906-998: The system is translationally-invariant, its local Hamiltonian problem becomes QMA EXP -complete (as the problem input is encoded in the system size, the verifier now has exponential runtime while maintaining the same promise gap). QMA-hardness results are known for simple lattice models of qubits such as the ZX Hamiltonian H Z X = ∑ i h i Z i + ∑ i Δ i X i + ∑ i < j J i j Z i Z j + ∑ i < j K i j X i X j {\displaystyle H_{ZX}=\sum _{i}h_{i}Z_{i}+\sum _{i}\Delta _{i}X_{i}+\sum _{i<j}J^{ij}Z_{i}Z_{j}+\sum _{i<j}K^{ij}X_{i}X_{j}} where Z , X {\displaystyle Z,X} represent

3969-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

#547452