Information Technology Reference
In-Depth Information
circuit families. Bernstein and Vazirani [50] showed that quantum gates of
only logarithmic accuracy suffice for polynomial time quantum circuits.
Aharonov et al. [77] discusses a generalization of quantum circuits to allow
mixed states, where measurements can be done in the middle of the
computation, and showed that such quantum circuits are equivalent in
computational power to standard quantum circuits. This generalized an
earlier result of Bernstein and Vazirani [50] that showed that all observa-
tion operations can be pushed to the end of the computation by repeated
use of a quantum XOR gate construction. Aharonov et al. [78] considered
an adiabatic model of quantum computation and showed it is equivalent to
standard quantum computation.
Computer Simulations of QC. Obenland, Despain [79-81] have given
efficient computer simulations of QC, including errors and decoherence,
and Cerf, Koonin [82] have given Monte Carlo simulations of QC.
3.3. COMPLEXITY BOUNDS FOR QC
3.3.1. Quantum Complexity Classes and Structural Complexity
Berthiaume, Brassard [83] survey open QC structural complexity problems (also
see Berthiaume [84]). QC can clearly execute deterministic and randomized
computations with no slow down. P (NP, QP, respectively) are the class of
problems solved by deterministic (nondeterministic, quantum, respectively) poly-
nomial time computations. Thus QP is the quantum analog of the time efficient
class P. It is not known if QP contains NP, that is, if QC can solve NP search
problems in polynomial time. It is also not known whether QP is a superset of P,
nor if there are any problems QC can solve in polynomial time that are not in P
(but this is true given quantum oracles; see Berthiaume, Brassard [85, 86], Machta
[87], and van Dam [88, 89] for complexity bounds for computing with quantum
oracles).
3.3.2. Bounded Precision QC
Let BQP be the class of polynomial time quantum computations that are
computed within bounded error. Most of the algorithms we will mention (such
as Shor's) are in the class BQP [50]. Showed that BQP computations can be done
using unitary operations with a fixed irrational rotation. Adleman et al. [90]
improved this to show that BQP can be computed using only unitary operations
with rational rotations, and that BQP is in the class PSPACE of polynomial space
computations of (classical) TMs. Practical implementations of QC most likely will
need to be done via unitary transitions within some modest amplitude precision.
Bernstein, Vazirani [50] proved that BQP computations running in time T can be
done with unitary operations specified by only O(log T) bits of precision.
 
Search WWH ::




Custom Search