Oblivious Amplitude Amplification
The following demo will exaplin the Oblivious Amplitude Amplification algorithm (OAA) [2], which can be used as a building block in algorithms such as hamiltonian simulations. We start with a short recap, then show how to use it in conjunction with the Linear Combination of Unitaries (LCU) algorithm.
Problem formulation
-
Input: A \((s, l, 0)\)-block-encoding \(W\) of a matrix \(U\).
-
Promise: \(U\) is unitary (or close to unitary).
-
Output: A \((1, l, 0)\)-block-encoding of \(U\).
Background
Recap - Amplitude Amplification
Ref. [1] shows how to use the Grover operator in order to amplify specific state. In detail, given a unitary \(A\) to prepare a state \(|\psi\rangle\):
And a unitary \(R_{\psi_1}\) to implement a reflection over the state \(\psi_1\), which we want to decrease its amplitude.
\(|\psi_0\rangle\), \(|\psi_1\rangle\) define a 2-dimensinal subspace where the applications of the grover operator are effectively rotations. To do that we also need to do a reflection about the initial state \(|\psi\rangle\):
where \(R_0\) is a reflection about the \(|0\rangle\) state.
The rotations can be used to take the initial vector \(|\psi\rangle\) closer to \(|\psi_0\rangle\).
Why do we need another version of Amplitude Amplification?
As you might have noticed, the amplification require to have the "recipe" \(A\) for the preparation of \(\psi\), and to use it in order to perform the reflection about the initial state.
In certain scenarios, such as in hamiltonian simulation, we might not be able to create the initial state, or it will be very non-efficient. Specifically, let us look on a \((s, l, 0)\)-block-encoding \(W\) of a matrix \(U\):
(For a detailed explanations about block encodings and hamiltonian simiulation, see this demo.
We want to amplify the amplitude of the state that is in the block, i.e. \(|0^l\rangle U|\psi\rangle\). This sometimes can be done in post-selection, but if we use \(W\) more than once in the algorithm, then the amplitude to sample the "good" states will exponentially decrease.
It turns out however, that if \(U\) is unitary, then we can reflect about the initial state \(W|0^l\rangle|\psi\rangle\) for any \(|\psi\rangle\), using the operator \(WRW^\dagger\) where \(R=(I-2|0^l\rangle\langle0^l|\otimes) I\) which is analogus to the reflection about the zero state. Then we get the same effective 2d picture! So in order to get \(|0^l\rangle U |\psi\rangle\) with probability \(\thicksim 1\), around \(\thicksim s\) Grover iterations are needed.
How to Build the Algorithm with Classiq
Example: Unitary LCU amplification
Here we take the matrix \(A = H_0\otimes H_1 = \frac{X_0 + Z_0} {\sqrt{2}} \otimes \frac{X_1 + Z_1} {\sqrt{2}}\) and block encode it using LCU, creating the matrix \(U_A\). In general, though LCU is a combination of unitaries, the result is not necessarily unitary. In this specific example, the matrix \(A\) is unitary, and so the encoding can be amplified using oblivious amplitude amplification.
Block Encoding the Hamiltonian
First show that the sampled state after the application of \(U_A\) is in the wanted block only in \(\frac {1}{4}\) of the cases, meaning that in this case \(s=2\). The input \(|\psi\rangle\) to \(U_A\) is a randomly sampled vector of normalized amplitudes.
import numpy as np
from classiq import *
PAULI_LIST = [
[Pauli.Z, Pauli.X],
[Pauli.X, Pauli.Z],
[Pauli.X, Pauli.X],
[Pauli.Z, Pauli.Z],
]
@qfunc
def apply_pauli_term(pauli_string: CArray[Pauli], x: QArray[QBit]):
repeat(
count=x.len,
iteration=lambda index: switch(
pauli_string[index],
[
lambda: IDENTITY(x[pauli_string.len - index - 1]),
lambda: X(x[pauli_string.len - index - 1]),
lambda: Y(x[pauli_string.len - index - 1]),
lambda: Z(x[pauli_string.len - index - 1]),
],
),
)
@qfunc
def block_encode(pauli_list: CArray[CArray[Pauli]], data: QArray[QBit], block: QNum):
within_apply(
lambda: hadamard_transform(block),
lambda: repeat(
count=pauli_list.len,
iteration=lambda i: control(
block == i, lambda: apply_pauli_term(pauli_list[i], data)
),
),
)
@qfunc
def main(data: Output[QNum], block: Output[QNum]):
allocate(2, block)
# initialize a random vector
np.random.seed(1)
amps = np.random.rand(4)
amps = (amps / np.linalg.norm(amps)).tolist()
prepare_amplitudes(amps, 0, data)
block_encode(PAULI_LIST, data, block)
qmod = create_model(main)
qprog = synthesize(qmod)
result = execute(qprog).result_value()
Print the "good" states:
block_sum = sum([d.shots for d in result.parsed_counts if d.state["block"] == 0])
for d in result.parsed_counts:
if d.state["block"] == 0:
print(d)
print("Fraction of `good` states:", block_sum / result.num_shots)
state={'data': 0.0, 'block': 0.0} shots=331
state={'data': 2.0, 'block': 0.0} shots=118
state={'data': 1.0, 'block': 0.0} shots=56
Fraction of `good` states: 0.24658203125
Block Encoding Amplification
Now we wrap \(U_A\) with the oblivious amplitude amplification scheme. It is almost like regular grover, except that it does not take the initial state preparation to the grover operator. Also, the grover diffuser only works on the block qubits (we take advantage of the language capturing mechanism).
The block_oracle (\(R\) in the used notation) operates on the block qubits and checks that they are in the wanted block (i.e. equal to the state \(|00\rangle\)). The \(W\) operator is represented by the function block_encoding.
As the original total amplitude of the "good states" is \(\frac{1}{2}\), exactly 1 grover iteration will amplify the amplitude to 1.
@qfunc
def block_oracle(var: QArray[QBit]):
block = QNum("block", 2, False, 0)
data = QArray("data")
bind(data, block)
@qfunc
def oblivious_amplitude_amplification(
reps: CInt,
block_encoding: QCallable[QNum, QArray[QBit]],
block: QNum,
data: QArray[QBit],
):
@qfunc
def check_block(b: QNum, res: QBit):
res ^= b == 0
block_encoding(data, block)
repeat(
reps,
lambda index: grover_operator(
lambda b: phase_oracle(lambda x, res: check_block(x, res), b),
lambda b: block_encoding(data, b),
block,
),
)
@qfunc
def main(data: Output[QNum], block: Output[QNum]):
allocate(2, block)
# initialize a random vector
np.random.seed(1)
amps = np.random.rand(4)
amps = (amps / np.linalg.norm(amps)).tolist()
prepare_amplitudes(amps, 0, data)
oblivious_amplitude_amplification(
1, lambda _block, _data: block_encode(PAULI_LIST, _block, _data), block, data
)
qmod_2 = create_model(main)
write_qmod(qmod_2, "oblivious_amplitude_amplification", decimal_precision=20)
qprog_2 = synthesize(qmod_2)
show(qprog_2)
result_2 = execute(qprog_2).result_value()
Opening: https://pre-release.platform.classiq.io/circuit/155e0033-3fb2-468e-955f-f3f3403e94e4?version=0.45.1
Print the "good" states:
block_sum_2 = sum([d.shots for d in result_2.parsed_counts if d.state["block"] == 0])
for d in result_2.parsed_counts:
if d.state["block"] == 0:
print(d)
state={'data': 0.0, 'block': 0.0} shots=1330
state={'data': 2.0, 'block': 0.0} shots=479
state={'data': 1.0, 'block': 0.0} shots=239
print("Fraction of `good` states:", block_sum_2 / result_2.num_shots)
assert block_sum_2 / result_2.num_shots == 1
Fraction of `good` states: 1.0
Extending to the case where \(U\) is non unitary
It was proven that when \(U\) is close to unitary, it is still possible to amplify (using the same operators) and get a good approximation. It was termed "Robust Oblivious Amplitude Amplification" [3]. This is usually the case in hamiltonian simulation when the LCU reprsents a truncated series which is only an approximation of the unitary \(e^{-iHt}\).
References
[1]: Brassard, Gilles, et al. "Quantum Amplitude Amplification and Estimation." arXiv preprint quant-ph/0005055 (2000).
[2]: Berry, Dominic W., et al. "Exponential improvement in precision for simulating sparse Hamiltonians." Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 2014.
[3]: Berry, Dominic W., et al. "Simulating Hamiltonian dynamics with a truncated Taylor series." Physical review letters 114.9 (2015): 090502.