# 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$$:

$A|0\rangle = |\psi\rangle = a|\psi_0\rangle + \sqrt{1-a^2}|\psi_1\rangle$

And a unitary $$R_{\psi_1}$$ to implement a reflection over the state $$\psi_1$$, which we want to decrease its amplitude.

$R_{\psi_1}(a|\psi_0\rangle + \sqrt{1-a^2}|\psi_1\rangle) = a|\psi+0\rangle - \sqrt{1-a^2}|\psi_1\rangle$

$$|\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$$:

$S_\psi = AR_0A^{\dagger}$

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$$:

$W|0^l\rangle|\psi\rangle = \frac{1}{s}|0^l\rangle U|\psi\rangle + \sqrt{1-\frac{1}{s^2}}|\phi\rangle$

(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: 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)
res = execute(qprog).result()[0].value


Print the "good" states:

block_sum = sum([d.shots for d in res.parsed_counts if d.state["block"] == 0])
for d in res.parsed_counts:
if d.state["block"] == 0:
print(d)
print("Fraction of good states:", block_sum / res.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 = create_model(main, out_file="oblivious_amplitude_amplification")
qprog = synthesize(qmod)
show(qprog)
res = execute(qprog).result()[0].value

Opening: https://pre-release.platform.classiq.io/circuit/155e0033-3fb2-468e-955f-f3f3403e94e4?version=0.45.1


Print the "good" states:

block_sum = sum([d.shots for d in res.parsed_counts if d.state["block"] == 0])
for d in res.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 / res.num_shots)
assert block_sum / res.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}$$.