Editing BQP (section)

==Definition==
'''BQP''' can be viewed as the [[Language (computability)|languages]] associated with certain bounded-error uniform families of [[quantum circuit]]s.<ref name=Chuang2000/> A language ''L'' is in '''BQP''' if and only if there exists a [[Circuit complexity#Polynomial-time uniform|polynomial-time uniform]] family of quantum circuits <math>\{Q_n\colon n \in \mathbb{N}\}</math>, such that
* For all <math>n \in \mathbb{N}</math>, ''Q<sub>n</sub>'' takes ''n'' qubits as input and outputs 1 bit
* For all ''x'' in ''L'', <math>\mathrm{Pr}(Q_{|x|}(x)=1)\geq \tfrac{2}{3}</math>
* For all ''x'' not in ''L'', <math>\mathrm{Pr}(Q_{|x|}(x)=0)\geq  \tfrac{2}{3}</math>

Alternatively, one can define '''BQP''' in terms of [[quantum Turing machine]]s. 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.<ref name="BernVazi">{{cite journal |last1=Bernstein |first1=Ethan |last2=Vazirani |first2=Umesh |title=Quantum Complexity Theory |journal=SIAM Journal on Computing |date=October 1997 |volume=26 |issue=5 |pages=1411–1473 |doi=10.1137/S0097539796300921 |ref=BernVazi|citeseerx=10.1.1.655.1186 }}</ref>

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 the [[Chernoff bound]]. The complexity class is unchanged by allowing error as high as 1/2 − ''n''<sup>−''c''</sup> on the one hand, or requiring error as small as 2<sup>−''n<sup>c</sup>''</sup> on the other hand, where ''c'' is any positive constant, and ''n'' is the length of input.<ref>{{cite book |last1=Barak |first1=Sanjeev Arora, Boaz |title=Computational Complexity: A Modern Approach / Sanjeev Arora and Boaz Barak |date=2009 |location=Cambridge |page=122 |url=https://www.cs.princeton.edu/theory/complexity/ |access-date=24 July 2018}}</ref>