Quantum Circuit - Quantum Computations

Quantum Computations

So far we have not shown how quantum circuits are used to perform computations. Since many important numerical problems reduce to computing a unitary transformation U on a finite dimensional space (the celebrated discrete Fourier transform being a prime example), one might expect that some quantum circuit could be designed to carry out the transformation U. In principle, one needs only to prepare an n qubit state ψ as an appropriate superposition of computational basis states for the input and measure the output Uψ. Unfortunately, there are two problems with this:

• One cannot measure the phase of ψ at any computational basis state so there is no way of reading out the complete answer. This is in the nature of measurement in quantum mechanics.

• There is no way to efficiently prepare the input state ψ.

This does not prevent quantum circuits for the discrete Fourier transform from being used as intermediate steps in other quantum circuits, but the use is more subtle. In fact quantum computations are probabilistic.

We now provide a mathematical model for how quantum circuits can simulate probabilistic but classical computations. Consider an r-qubit circuit U with register space H_QB(r). U is thus a unitary map

In order to associate this circuit to a classical mapping on bitstrings, we specify

• An input register X = {0,1}m of m (classical) bits.

• An output register Y = {0,1}n of n (classical) bits.

The contents x = x₁, ..., x_m of the classical input register are used to initialize the qubit register in some way. Ideally, this would be done with the computational basis state

where there are r-m underbraced zeroed inputs. Nevertheless, this perfect initialization is completely unrealistic. Let us assume therefore that the initialization is a mixed state given by some density operator S which is near the idealized input in some appropriate metric, e.g.

Similarly, the output register space is related to the qubit register, by a Y valued observable A. Note that observables in quantum mechanics are usually defined in terms of projection valued measures on R; if the variable happens to be discrete, the projection valued measure reduces to a family {E_λ} indexed on some parameter λ ranging over a countable set. Similarly, a Y valued observable, can be associated with a family of pairwise orthogonal projections {E_y} indexed by elements of Y. such that

Given a mixed state S, there corresponds a probability measure on Y given by

The function F:X → Y is computed by a circuit U:H_QB(r) → H_QB(r) to within ε if and only if for all bitstrings x of length m

Now

so that

Theorem. If ε+ δ <1/2, then the probability distribution

on Y can be used to determine F(x) with an arbitrarily small probability of error by majority sampling, for a sufficiently large sample size. Specifically, take k independent samples from the probability distribution Pr on Y and choose a value on which more than half of the samples agree. The probability that the value F(x) is sampled more than k/2 times is at least

where γ = 1/2 -ε - δ.

This follows by applying the Chernoff bound.