Hands-on 7

Grover’s Algorithm and Amplitude Amplification

Grover’s algorithm is one of the most famous quantum algorithms introduced by Lov Grover in 1996 [1]. It has initially been proposed for unstructured search problems, i.e. for finding a marked element in a unstructured database. However, Grover’s algorithm is now a subroutine to several other algorithms, such as Grover Adaptive Search [2].

Qiskit implements Grover’s algorithm in the Grover class. This class also includes the generalized version, Amplitude Amplification [3], and allows setting individual iterations and other meta-settings to Grover’s algorithm.

References:

[1]: L. K. Grover, A fast quantum mechanical algorithm for database search. Proceedings 28th Annual Symposium on the Theory of Computing (STOC) 1996, pp. 212-219. https://arxiv.org/abs/quant-ph/9605043

[2]: A. Gilliam, S. Woerner, C. Gonciulea, Grover Adaptive Search for Constrained Polynomial Binary Optimization. https://arxiv.org/abs/1912.04088

[3]: Brassard, G., Hoyer, P., Mosca, M., & Tapp, A. (2000). Quantum Amplitude Amplification and Estimation. http://arxiv.org/abs/quant-ph/0005055

Grover’s algorithm

Grover’s algorithm uses the Grover operator \(\mathcal{Q}\) to amplify the amplitudes of the good states:

\[ \mathcal{Q} = \mathcal{A}\mathcal{S_0}\mathcal{A}^\dagger \mathcal{S_f} \]

Here,

• \(\mathcal{A}\) is the initial search state for the algorithm, which is just Hadamards, \(H^{\otimes n}\) for the textbook Grover search, but can be more elaborate for Amplitude Amplification

• \(\mathcal{S_0}\) is the reflection about the all 0 state $\( |x\rangle \mapsto \begin{cases} -|x\rangle, &x \neq 0 \\ |x\rangle, &x = 0\end{cases} \)$

• \(\mathcal{S_f}\) is the oracle that applies $\( |x\rangle \mapsto (-1)^{f(x)}|x\rangle \)\( 　 where \)f(x)\( is 1 if \)x$ is a good state and otherwise 0.

In a nutshell, Grover’s algorithm applies different powers of \(\mathcal{Q}\) and after each execution checks whether a good solution has been found.

Running Grover’s algorithm

To run Grover’s algorithm with the Grover class, firstly, we need to specify an oracle for the circuit of Grover’s algorithm. In the following example, we use QuantumCircuit as the oracle of Grover’s algorithm. However, there are several other class that we can use as the oracle of Grover’s algorithm. We talk about them later in this tutorial.

Note that the oracle for Grover must be a phase-flip oracle. That is, it multiplies the amplitudes of the of “good states” by a factor of \(-1\). We explain later how to convert a bit-flip oracle to a phase-flip oracle.

from qiskit import QuantumCircuit
from qiskit.algorithms import AmplificationProblem

# the state we desire to find is '11'
good_state = ['11']

# specify the oracle that marks the state '11' as a good solution
oracle = QuantumCircuit(2)
oracle.cz(0, 1)

# define Grover's algorithm
problem = AmplificationProblem(oracle, is_good_state=good_state)

# now we can have a look at the Grover operator that is used in running the algorithm
# (Algorithm circuits are wrapped in a gate to be appear in composition as a block
# so we have to decompose() the op to see it expanded into its component gates.)
problem.grover_operator.decompose().draw(output='mpl')

Then, we specify a backend and call the run method of Grover with a backend to execute the circuits. The returned result type is a GroverResult.

If the search was successful, the oracle_evaluation attribute of the result will be True. In this case, the most sampled measurement, top_measurement, is one of the “good states”. Otherwise, oracle_evaluation will be False.

from qiskit import Aer
from qiskit.utils import QuantumInstance
from qiskit.algorithms import Grover

aer_simulator = Aer.get_backend('aer_simulator')
grover = Grover(quantum_instance=aer_simulator)
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

In the example, the result of top_measurement is 11 which is one of “good state”. Thus, we succeeded to find the answer by using Grover.

Using the different types of classes as the oracle of Grover

In the above example, we used QuantumCircuit as the oracle of Grover. However, we can also use qiskit.quantum_info.Statevector as oracle. All the following examples are when \(|11\rangle\) is “good state”

from qiskit.quantum_info import Statevector
oracle = Statevector.from_label('11')
problem = AmplificationProblem(oracle, is_good_state=['11'])

grover = Grover(quantum_instance=aer_simulator)
result = grover.amplify(problem)
print('Result type:', type(result))
print()
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Result type: <class 'qiskit.algorithms.amplitude_amplifiers.grover.GroverResult'>

Success!
Top measurement: 11

Internally, the statevector is mapped to a quantum circuit:

problem.grover_operator.oracle.decompose().draw(output='mpl')

Qiskit allows for an easy construction of more complex oracles:

• PhaseOracle: for parsing logical expressions such as '~a | b'. This is especially useful for solving 3-SAT problems.

Here we’ll use the PhaseOracle for the simple example of finding the state \(|11\rangle\), which corresponds to 'a & b'.

from qiskit.circuit.library.phase_oracle import PhaseOracle
from qiskit.exceptions import MissingOptionalLibraryError

# `Oracle` (`PhaseOracle`) as the `oracle` argument
expression = '(a & b)'
try:
    oracle = PhaseOracle(expression)
    problem = AmplificationProblem(oracle)
    display(problem.grover_operator.oracle.decompose().draw(output='mpl'))
except MissingOptionalLibraryError as ex:
    print(ex)

You can observe, that this oracle is actually implemented with three qubits instead of two!

That is because the PhaseOracle is not a phase-flip oracle (which flips the phase of the good state) but a bit-flip oracle. This means it flips the state of an auxiliary qubit if the other qubits satisfy the condition. For Grover’s algorithm, however, we require a phase-flip oracle. To convert the bit-flip oracle to a phase-flip oracle we sandwich the controlled-NOT by \(X\) and \(H\) gates, as you can see in the circuit above.

Note: This transformation from a bit-flip to a phase-flip oracle holds generally and you can use this to convert your oracle to the right representation.

Amplitude amplification

Grover’s algorithm uses Hadamard gates to create the uniform superposition of all the states at the beginning of the Grover operator \(\mathcal{Q}\). If some information on the good states is available, it might be useful to not start in a uniform superposition but only initialize specific states. This, generalized, version of Grover’s algorithm is referred to Amplitude Amplification.

In Qiskit, the initial superposition state can easily be adjusted by setting the state_preparation argument.

State preparation

A state_preparation argument is used to specify a quantum circuit that prepares a quantum state for the start point of the amplitude amplification. By default, a circuit with \(H^{\otimes n}\) is used to prepare uniform superposition (so it will be Grover’s search). The diffusion circuit of the amplitude amplification reflects state_preparation automatically.

import numpy as np

# Specifying `state_preparation` 
# to prepare a superposition of |01>, |10>, and |11>
oracle = QuantumCircuit(3)
oracle.h(2)
oracle.ccx(0,1,2)
oracle.h(2)

theta = 2 * np.arccos(1 / np.sqrt(3))
state_preparation = QuantumCircuit(3)
state_preparation.ry(theta, 0)
state_preparation.ch(0,1)
state_preparation.x(1)
state_preparation.h(2)

# we only care about the first two bits being in state 1, thus add both possibilities for the last qubit
problem = AmplificationProblem(oracle, state_preparation=state_preparation, is_good_state=['110', '111'])

# state_preparation
print('state preparation circuit:')
problem.grover_operator.state_preparation.draw(output='mpl')

state preparation circuit:

grover = Grover(quantum_instance=aer_simulator)
result = grover.amplify(problem)
print('Success!' if result.oracle_evaluation else 'Failure!')
print('Top measurement:', result.top_measurement)

Success!
Top measurement: 111

Full flexibility

For more advanced use, it is also possible to specify the entire Grover operator by setting the grover_operator argument. This might be useful if you know more efficient implementation for \(\mathcal{Q}\) than the default construction via zero reflection, oracle and state preparation.

The qiskit.circuit.library.GroverOperator can be a good starting point and offers more options for an automated construction of the Grover operator. You can for instance

• set the mcx_mode

• ignore qubits in the zero reflection by setting reflection_qubits

• explicitly exchange the \(\mathcal{S_f}, \mathcal{S_0}\) and \(\mathcal{A}\) operations using the oracle, zero_reflection and state_preparation arguments

For instance, imagine the good state is a three qubit state \(|111\rangle\) but we used 2 additional qubits as auxiliary qubits.

from qiskit.circuit.library import GroverOperator, ZGate

oracle = QuantumCircuit(5)
oracle.append(ZGate().control(2), [0, 1, 2])
oracle.draw(output='mpl')

Then, per default, the Grover operator implements the zero reflection on all five qubits.

grover_op = GroverOperator(oracle, insert_barriers=True)
grover_op.decompose().draw(output='mpl')

But we know that we only need to consider the first three:

grover_op = GroverOperator(oracle, reflection_qubits=[0, 1, 2], insert_barriers=True)
grover_op.decompose().draw(output='mpl')

Dive into other arguments of Grover

Grover has arguments other than oracle and state_preparation. We will explain them in this section.

Specifying good_state

good_state is used to check whether the measurement result is correct or not internally. It can be a list of binary strings, a list of integer, Statevector, and Callable. If the input is a list of bitstrings, each bitstrings in the list represents a good state. If the input is a list of integer, each integer represent the index of the good state to be \(|1\rangle\). If it is a Statevector, it represents a superposition of all good states.

# a list of binary strings good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = ['11', '00']
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

# a list of integer good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = [0, 1]
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

from qiskit.quantum_info import Statevector

# `Statevector` good state
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
good_state = Statevector.from_label('11')
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

# Callable good state
def callable_good_state(bitstr):
    if bitstr == "11":
        return True
    return False

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=good_state)
print(problem.is_good_state('11'))

True

The number of iterations

The number of repetition of applying the Grover operator is important to obtain the correct result with Grover’s algorithm. The number of iteration can be set by the iteration argument of Grover. The following inputs are supported:

• an integer to specify a single power of the Grover operator that’s applied

• or a list of integers, in which all these different powers of the Grover operator are run consecutively and after each time we check if a correct solution has been found

Additionally there is the sample_from_iterations argument. When it is True, instead of the specific power in iterations, a random integer between 0 and the value in iteration is used as the power Grover’s operator. This approach is useful when we don’t even know the number of solution.

For more details of the algorithm using sample_from_iterations, see [4].

References:

[4]: Boyer et al., Tight bounds on quantum searching arxiv:quant-ph/9605034

# integer iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=1)

# list iteration
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=[1, 2, 3])

# using sample_from_iterations
oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'])
grover = Grover(iterations=[1, 2, 3], sample_from_iterations=True)

When the number of solutions is known, we can also use a static method optimal_num_iterations to find the optimal number of iterations. Note that the output iterations is an approximate value. When the number of qubits is small, the output iterations may not be optimal.

iterations = Grover.optimal_num_iterations(num_solutions=1, num_qubits=8)
iterations

12

Applying post_processing

We can apply an optional post processing to the top measurement for ease of readability. It can be used e.g. to convert from the bit-representation of the measurement [1, 0, 1] to a DIMACS CNF format [1, -2, 3].

def to_DIAMACS_CNF_format(bit_rep):
    return [index+1 if val==1 else -1 * (index + 1) for index, val in enumerate(bit_rep)]

oracle = QuantumCircuit(2)
oracle.cz(0, 1)
problem = AmplificationProblem(oracle, is_good_state=['11'], post_processing=to_DIAMACS_CNF_format)
problem.post_processing([1, 0, 1])

[1, -2, 3]

Grover’s algorithm examples

This notebook has examples demonstrating how to use the Qiskit Grover search algorithm, with different oracles.

import pylab
import numpy as np
from qiskit import Aer
from qiskit.utils import QuantumInstance
from qiskit.tools.visualization import plot_histogram
from qiskit.algorithms import Grover, AmplificationProblem
from qiskit.circuit.library.phase_oracle import PhaseOracle

Finding solutions to 3-SAT problems

Let’s look at an example 3-Satisfiability (3-SAT) problem and walk-through how we can use Quantum Search to find its satisfying solutions. 3-SAT problems are usually expressed in Conjunctive Normal Forms (CNF) and written in the DIMACS-CNF format. For example:

input_3sat_instance = '''
c example DIMACS-CNF 3-SAT
p cnf 3 5
-1 -2 -3 0
1 -2 3 0
1 2 -3 0
1 -2 -3 0
-1 2 3 0
'''

The CNF of this 3-SAT instance contains 3 variables and 5 clauses:

\((\neg v_1 \vee \neg v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee v_3) \wedge (v_1 \vee v_2 \vee \neg v_3) \wedge (v_1 \vee \neg v_2 \vee \neg v_3) \wedge (\neg v_1 \vee v_2 \vee v_3)\)

It can be verified that this 3-SAT problem instance has three satisfying solutions:

\((v_1, v_2, v_3) = (T, F, T)\) or \((F, F, F)\) or \((T, T, F)\)

Or, expressed using the DIMACS notation:

1 -2 3, or -1 -2 -3, or 1 2 -3.

With this example problem input, we then create the corresponding oracle for our Grover search. In particular, we use the PhaseOracle component, which supports parsing DIMACS-CNF format strings and constructing the corresponding oracle circuit.

import os
import tempfile
from qiskit.exceptions import MissingOptionalLibraryError

fp = tempfile.NamedTemporaryFile(mode='w+t', delete=False)
fp.write(input_3sat_instance)
file_name = fp.name
fp.close()
oracle = None
try:
    oracle = PhaseOracle.from_dimacs_file(file_name)
except MissingOptionalLibraryError as ex:
    print(ex)
finally:
    os.remove(file_name)

The oracle can now be used to create an Grover instance:

problem = None
if oracle is not None:
    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)

We can then configure the backend and run the Grover instance to get the result:

backend = Aer.get_backend('aer_simulator')
quantum_instance = QuantumInstance(backend, shots=1024)
grover = Grover(quantum_instance=quantum_instance)
result = None
if problem is not None:
    result = grover.amplify(problem)
    print(result.assignment)

101

As seen above, a satisfying solution to the specified 3-SAT problem is obtained. And it is indeed one of the three satisfying solutions.

Since we used the 'aer_simulator', the complete measurement result is also returned, as shown in the plot below, where it can be seen that the binary strings 000, 011, and 101 (note the bit order in each string), corresponding to the three satisfying solutions all have high probabilities associated with them.

if result is not None:
    display(plot_histogram(result.circuit_results[0]))

Boolean Logical Expressions

Qiskit’s Grover can also be used to perform Quantum Search on an Oracle constructed from other means, in addition to DIMACS. For example, the PhaseOracle can actually be configured using arbitrary Boolean logical expressions, as demonstrated below.

expression = '(w ^ x) & ~(y ^ z) & (x & y & z)'
try:
    oracle = PhaseOracle(expression)
    problem = AmplificationProblem(oracle, is_good_state=oracle.evaluate_bitstring)
    grover = Grover(quantum_instance=QuantumInstance(Aer.get_backend('aer_simulator'), shots=1024))
    result = grover.amplify(problem)
    display(plot_histogram(result.circuit_results[0]))
except MissingOptionalLibraryError as ex:
    print(ex)

In the example above, the input Boolean logical expression '(w ^ x) & ~(y ^ z) & (x & y & z)' should be quite self-explanatory, where ^, ~, and & represent the Boolean logical XOR, NOT, and AND operators, respectively. It should be quite easy to figure out the satisfying solution by examining its parts: w ^ x calls for w and x taking different values; ~(y ^ z) requires y and z be the same; x & y & z dictates all three to be True. Putting these together, we get the satisfying solution (w, x, y, z) = (False, True, True, True), which our Grover’s result agrees with.

Quantum Amplitude Estimation

Given an operator \(\mathcal{A}\) that acts as

\[ \mathcal{A}|0\rangle = \sqrt{1 - a}|\Psi_0\rangle + \sqrt{a}|\Psi_1\rangle \]

Quantum Amplitude Estimation (QAE) is the task of finding an estimate for the amplitude \(a\) of the state \(|\Psi_1\rangle\):

\[ a = |\langle\Psi_1 | \Psi_1\rangle|^2. \]

This task has first been investigated by Brassard et al. [1] in 2000 and their algorithm uses a combination of the Grover operator

\[ \mathcal{Q} = \mathcal{A}\mathcal{S}_0\mathcal{A}^\dagger\mathcal{S}_{\Psi_1} \]

where \(\mathcal{S}_0\) and \(\mathcal{S}_{\Psi_1}\) are reflections about the \(|0\rangle\) and \(|\Psi_1\rangle\) states, respectively, and phase estimation. However this algorithm, called AmplitudeEstimation in Qiskit, requires large circuits and is computationally expensive. Therefore, other variants of QAE have been proposed, which we will showcase in this tutorial for a simple example.

In our example, \(\mathcal{A}\) describes a Bernoulli random variable with (assumed to be unknown) success probability \(p\):

\[ \mathcal{A}|0\rangle = \sqrt{1 - p}|0\rangle + \sqrt{p}|1\rangle. \]

On a quantum computer, we can model this operator with a rotation around the \(Y\)-axis of a single qubit

\[ \mathcal{A} = R_Y(\theta_p), \theta_p = 2\sin^{-1}(\sqrt{p}). \]

The Grover operator for this case is particularly simple

\[ \mathcal{Q} = R_Y(2\theta_p), \]

whose powers are very easy to calculate: \(\mathcal{Q}^k = R_Y(2k\theta_p)\).

We’ll fix the probability we want to estimate to \(p = 0.2\).

p = 0.2

Now we can define circuits for \(\mathcal{A}\) and \(\mathcal{Q}\).

import numpy as np
from qiskit.circuit import QuantumCircuit


class BernoulliA(QuantumCircuit):
    """A circuit representing the Bernoulli A operator."""

    def __init__(self, probability):
        super().__init__(1)  # circuit on 1 qubit

        theta_p = 2 * np.arcsin(np.sqrt(probability))
        self.ry(theta_p, 0)


class BernoulliQ(QuantumCircuit):
    """A circuit representing the Bernoulli Q operator."""

    def __init__(self, probability):
        super().__init__(1)  # circuit on 1 qubit

        self._theta_p = 2 * np.arcsin(np.sqrt(probability))
        self.ry(2 * self._theta_p, 0)

    def power(self, k):
        # implement the efficient power of Q
        q_k = QuantumCircuit(1)
        q_k.ry(2 * k * self._theta_p, 0)
        return q_k

A = BernoulliA(p)
Q = BernoulliQ(p)

Qiskit’s Amplitude Estimation workflow

Qiskit implements several QAE algorithms that all derive from the AmplitudeEstimator interface. In the initializer we specify algorithm specific settings and the estimate method, which does all the work, takes an EstimationProblem as input and returns an AmplitudeEstimationResult object. Since all QAE variants follow the same interface, we can use them all to solve the same problem instance.

Next, we’ll run all different QAE algorithms. To do so, we first define the estimation problem which will contain the \(\mathcal{A}\) and \(\mathcal{Q}\) operators as well as how to identify the \(|\Psi_1\rangle\) state, which in this simple example is just \(|1\rangle\).

from qiskit.algorithms import EstimationProblem

problem = EstimationProblem(
    state_preparation=A,  # A operator
    grover_operator=Q,  # Q operator
    objective_qubits=[0],  # the "good" state Psi1 is identified as measuring |1> in qubit 0
)

To execute circuits we’ll use Qiskit’s statevector simulator.

from qiskit import BasicAer
from qiskit.utils import QuantumInstance

backend = BasicAer.get_backend("statevector_simulator")
quantum_instance = QuantumInstance(backend)

Canonical AE

Now let’s solve this with the original QAE implementation by Brassard et al. [1].

from qiskit.algorithms import AmplitudeEstimation

ae = AmplitudeEstimation(
    num_eval_qubits=3,  # the number of evaluation qubits specifies circuit width and accuracy
    quantum_instance=quantum_instance,
)

With the algorithm defined, we can call the estimate method and provide it with the problem to solve.

ae_result = ae.estimate(problem)

The estimate is available in the estimation key:

print(ae_result.estimation)

0.1464466

We see that this is not a very good estimate for our target of \(p=0.2\)! That’s due to the fact the canonical AE is restricted to a discrete grid, specified by the number of evaluation qubits:

import matplotlib.pyplot as plt

# plot estimated values
gridpoints = list(ae_result.samples.keys())
probabilities = list(ae_result.samples.values())

plt.bar(gridpoints, probabilities, width=0.5 / len(probabilities))
plt.axvline(p, color="r", ls="--")
plt.xticks(size=15)
plt.yticks([0, 0.25, 0.5, 0.75, 1], size=15)
plt.title("Estimated Values", size=15)
plt.ylabel("Probability", size=15)
plt.xlabel(r"Amplitude $a$", size=15)
plt.ylim((0, 1))
plt.grid()
plt.show()

To improve the estimate we can interpolate the measurement probabilities and compute the maximum likelihood estimator that produces this probability distribution:

print("Interpolated MLE estimator:", ae_result.mle)

Interpolated MLE estimator: 0.19999999390907777

We can have a look at the circuit that AE executes:

ae_circuit = ae.construct_circuit(problem)
ae_circuit.decompose().draw(
    "mpl", style="iqx"
)  # decompose 1 level: exposes the Phase estimation circuit!

/home/obm/Prog/miniconda3/envs/qml/lib/python3.8/site-packages/qiskit/visualization/circuit/matplotlib.py:163: UserWarning: Style JSON file 'iqx.json' not found in any of these locations: /home/obm/Prog/miniconda3/envs/qml/lib/python3.8/site-packages/qiskit/visualization/circuit/styles/iqx.json, iqx.json. Will use default style.
  self._style, def_font_ratio = load_style(style)

from qiskit import transpile


basis_gates = ["h", "ry", "cry", "cx", "ccx", "p", "cp", "x", "s", "sdg", "y", "t", "cz"]
transpile(ae_circuit, basis_gates=basis_gates, optimization_level=2).draw("mpl", style="iqx")

/home/obm/Prog/miniconda3/envs/qml/lib/python3.8/site-packages/qiskit/visualization/circuit/matplotlib.py:163: UserWarning: Style JSON file 'iqx.json' not found in any of these locations: /home/obm/Prog/miniconda3/envs/qml/lib/python3.8/site-packages/qiskit/visualization/circuit/styles/iqx.json, iqx.json. Will use default style.
  self._style, def_font_ratio = load_style(style)

Iterative Amplitude Estimation

See [2].

from qiskit.algorithms import IterativeAmplitudeEstimation

iae = IterativeAmplitudeEstimation(
    epsilon_target=0.01,  # target accuracy
    alpha=0.05,  # width of the confidence interval
    quantum_instance=quantum_instance,
)
iae_result = iae.estimate(problem)

print("Estimate:", iae_result.estimation)

Estimate: 0.19999999999999998

The circuits here only consist of Grover powers and are much cheaper!

iae_circuit = iae.construct_circuit(problem, k=3)
iae_circuit.draw("mpl", style="iqx")

/home/obm/Prog/miniconda3/envs/qml/lib/python3.8/site-packages/qiskit/visualization/circuit/matplotlib.py:163: UserWarning: Style JSON file 'iqx.json' not found in any of these locations: /home/obm/Prog/miniconda3/envs/qml/lib/python3.8/site-packages/qiskit/visualization/circuit/styles/iqx.json, iqx.json. Will use default style.
  self._style, def_font_ratio = load_style(style)

Maximum Likelihood Amplitude Estimation

See [3].

from qiskit.algorithms import MaximumLikelihoodAmplitudeEstimation

mlae = MaximumLikelihoodAmplitudeEstimation(
    evaluation_schedule=3, quantum_instance=quantum_instance  # log2 of the maximal Grover power
)
mlae_result = mlae.estimate(problem)

print("Estimate:", mlae_result.estimation)

Estimate: 0.20002237175368104

Faster Amplitude Estimation

See [4].

from qiskit.algorithms import FasterAmplitudeEstimation

fae = FasterAmplitudeEstimation(
    delta=0.01,  # target accuracy
    maxiter=3,  # determines the maximal power of the Grover operator
    quantum_instance=quantum_instance,
)
fae_result = fae.estimate(problem)

print("Estimate:", fae_result.estimation)

Estimate: 0.20000000000000018

/home/obm/Prog/miniconda3/envs/qml/lib/python3.8/site-packages/qiskit/algorithms/amplitude_estimators/estimation_problem.py:195: UserWarning: Rescaling discards the Grover operator.
  warnings.warn("Rescaling discards the Grover operator.")

References

[1] Quantum Amplitude Amplification and Estimation. Brassard et al (2000). https://arxiv.org/abs/quant-ph/0005055

[2] Iterative Quantum Amplitude Estimation. Grinko, D., Gacon, J., Zoufal, C., & Woerner, S. (2019). https://arxiv.org/abs/1912.05559

[3] Amplitude Estimation without Phase Estimation. Suzuki, Y., Uno, S., Raymond, R., Tanaka, T., Onodera, T., & Yamamoto, N. (2019). https://arxiv.org/abs/1904.10246

[4] Faster Amplitude Estimation. K. Nakaji (2020). https://arxiv.org/pdf/2003.02417.pdf

Send it after class

Suppose we have a random variable \(X\) described by a certain probability distribution over \(N\) different outcomes, and a function \(f:\{0,\dots,N\} \mapsto [0,1]\) defined over this distribution. How can we use quantum computers to evaluate

1. Expectation value of \(X\)

2. Variance of \(X\) Tip: The probability distribution is represented in our quantum computer by a quantum state over \(n=⌈\log N⌉\) qubits as \( \left|\psi\right\rangle = \sum_{i=0}^{N-1} \sqrt{p_i} \left|i\right\rangle \). You can quantize the function \(f\) using an ancilla qubit as \(F: \left|i\right\rangle \left|0\right\rangle \mapsto \left|i\right\rangle \left( \sqrt{1-f(i) } \left|0\right\rangle +\sqrt{f(i) } \left|1\right\rangle \right)\)