This sample introduces iterative phase estimation, as well as the algorithms for processing the results of iterative phase estimation that are provided with Q#.
In phase estimation, one is concerned with learning the *eigenvalues*
of a unitary operator U. In particular, suppose that U is unknown, but
that we have access to U as an oracle. That is, we can call U as an
operation on a register of our choice, but cannot introspect into its
source code. Suppose as well that we also have access to an operation
which prepares a state |φ〉 such that U|φ〉 = e^{i φ} |φ〉 for some φ
that we would like to learn. Given these resources, we can learn φ by
applying either quantum or iterative phase estimation.
Before proceeding further, it’s helpful to take a moment to discuss
how to represent the phase estimation oracle U in our Q# programs.
The most straightforward representation is for any phase estimation
operation to take as an input a value of type
(Qubit[] => () : Controlled), representing an operation that acts on
an array of qubits and that can be controlled.
To implement U^m for some power m, we can use an operation of this form inside of a for loop. This precludes, however, if we have a more
efficient implementation that would let us “fast forward.”
By the no fast-forwarding theorem [https://arxiv.org/abs/0908.4398],
this cannot be done in general, such that if we only have oracular
access to U, we preclude significant opportunities for improvements.
A more general approach is thus to take an operation of type
((Int, Qubit[]) => () : Controlled) representing U(m) ≔ U^m.
For oracular access to U, we write out the same for loop here, or use
the OperationPow function in the canon, while we remain compatible with speedups in special cases.
As a further generalization, we can instead consider that U is not
a single unitary at all, but a family of unitaries parameterized by
time, |ψ(t)〉 = U(t) |ψ(0)〉. If these unitaries compose as U(t + s) =
U(t) U(s), then we can write that U(t) = e^{-i H t} for some operator
H, making this model ideal for application to Hamiltonian simulation.
In particular, we now have that |φ〉 is an eigenstate of H as well,
such that H|φ〉 = -φ|φ〉. Thus, phase estimation expressed in this form
learns the energy of a particular eigenstate of a Hamiltonian.
This generalization is represented in Q# as an operation of the type
((Double, Qubit[]) => () : Controlled).
For the rest of this sample, we follow the continuous-time convention.
In the iterative case, one learns φ by using
a single additional qubit to turn phase estimation into a classical
statistical problem.
Given an operation representing U and an operation representing
preparation of |φ〉, we can implement each step of iterative phase estimation by preparing a control qubit in the |+〉 state, controlling the application of U(t) for some t : Double, and then measuring the control qubit in the X basis.
The final measurement from a single step follows a sinusoidal
*likelihood function*, such that iterative phase estimation is readily
amenable to analysis by well-known methods such as Bayesian inference, as we will detail below. For now, we define the phase estimation step itself. In practice, it can help dramatically improve numerical stability of some algorithms if we also rotate the control qubit before using it
to control U. We thus include an additional input to allow
for this.
Having checked that the phase estimation iteration does indeed follow
the likelihood function we expected, we can proceed to learn the
phase. For this sample, we will follow the Bayesian formalism, and
will attempt to find the posterior distribution
Pr(φ | data) = Pr(data | φ) Pr(φ) / Pr(data),
where Pr(φ) is the prior distribution over φ, where Pr(data | φ) is the
likelihood function that we tested in the previous step, and where
Pr(data) = ∫ Pr(data | φ) Pr(φ) dφ is a normalization factor.
For simplicity, we will take Pr(φ) = 1 over the interval [0, 1] as our
prior.
The estimate ̂φ can then be found by integrating over the posterior,
̂φ ≔ ∫ φ Pr(φ | data) dφ.
We will use an explicit grid method, in which we discretize the prior
and posterior at each φ, effectively replacing the integrals above
with the trapezoidal rule.
It’s helpful in writing up Bayesian phase estimation with the explicit
grid method to first define a couple utility functions.
Next Blog article will have the implementation in Q#.
Q# laatste nieuws 