Editing BQP (section)

=== A complete problem for Promise-BQP ===

Promise-BQP is the class of [[promise problem|promise problems]] that can be solved by a uniform family of quantum circuits (i.e., within BQP).<ref name="janzing-wocjan">{{cite journal|last1=Janzing|first1=Dominik|last2=Wocjan|first2=Pawel|date=2007-03-30|title=A Simple PromiseBQP-complete Matrix Problem|url=https://theoryofcomputing.org/articles/v003a004/v003a004.pdf|journal=Theory of Computing|volume=3|issue=4|pages=61–79|doi=10.4086/toc.2007.v003a004|access-date=2024-04-18}}</ref> Completeness proofs focus on this version of BQP. Similar to the notion of [[NP-completeness]] and other [[complete (complexity)|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. 

==== APPROX-QCIRCUIT-PROB ====

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 the relationships between other complexity classes and BQP.

Given a description of a quantum circuit {{mvar|C}} acting on  {{mvar|n}} qubits with {{mvar|m}} gates, where  {{mvar|m}} is a polynomial in {{mvar|n}} and each gate acts on one or two qubits, and two numbers <math>\alpha, \beta \in [0,1], \alpha > \beta</math>, distinguish between the following two cases:
* measuring the first qubit of the state <math>C|0\rangle^{\otimes n}</math> yields <math>|1\rangle</math> with probability <math>\geq \alpha</math>
* measuring the first qubit of the state <math>C|0\rangle^{\otimes n}</math> yields <math>|1\rangle</math> with probability <math>\leq \beta</math>

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  {{mvar|A}} that solves APPROX-QCIRCUIT-PROB, i.e., given a quantum circuit {{mvar|C}} acting on  {{mvar|n}} qubits, and two numbers <math>\alpha, \beta \in [0,1], \alpha > \beta</math>, {{mvar|A}} distinguishes between the above two cases. We can solve any problem in BQP with this oracle, by setting <math>\alpha = 2/3, \beta = 1/3</math>.

For any <math>L \in \mathsf{BQP} </math>, there exists family of quantum circuits <math>\{Q_n\colon n \in \mathbb{N}\}</math> such that for all <math>n \in \mathbb{N}</math>, a state <math> |x\rangle </math> of  <math>n </math>  qubits, if <math>x \in L, Pr(Q_n(|x\rangle)=1) \geq 2/3</math>; else if  <math>x \notin L, Pr(Q_n(|x\rangle)=0) \geq 2/3 </math>. Fix an input <math> |x\rangle </math> of {{mvar|n}} qubits, and the corresponding quantum circuit <math>Q_n</math>. We can first construct a circuit <math>C_x</math> such that <math>C_x|0\rangle^{\otimes n} = |x\rangle</math>. This can be done easily by hardwiring <math> |x\rangle </math> and apply a sequence of [[Controlled NOT gate|CNOT]] gates to flip the qubits. Then we can combine two circuits to get <math>C' = Q_nC_x</math>, and now <math>C'|0\rangle^{\otimes n} = Q_n|x\rangle</math>. And finally, necessarily the results of <math>Q_n</math> is obtained by measuring several qubits and apply some (classical) logic gates to them. We can always [[Deferred Measurement Principle|defer the measurement]]<ref name="NielsenChuang2010">{{cite book|author1=Michael A. Nielsen|author2=Isaac L. Chuang|title=Quantum Computation and Quantum Information: 10th Anniversary Edition|url=https://books.google.com/books?id=-s4DEy7o-a0C|date=9 December 2010|publisher=Cambridge University Press|isbn=978-1-139-49548-6 |page=186 |section=4.4 Measurement}}</ref><ref name="Cross2012">{{cite book|author=Odel A. Cross|title=Topics in Quantum Computing|url=https://books.google.com/books?id=b_D9flK2h8QC&pg=PA348|date=5 November 2012|publisher=O. A. Cross|isbn=978-1-4800-2749-7|page=348 |section=5.2.2 Deferred Measurement}}</ref> and reroute the circuits so that by measuring the first qubit of <math>C'|0\rangle^{\otimes n} = Q_n|x\rangle</math>, we get the output. This will be our circuit {{mvar|C}}, and we decide the membership of <math>x \in L</math> by running  <math>A(C)</math> with <math>\alpha = 2/3, \beta = 1/3</math>. By definition of BQP, we will either fall into the first case (acceptance), or the second case (rejection), so <math>L \in \mathsf{BQP} </math> reduces to APPROX-QCIRCUIT-PROB.