Compression Gadget¶
We are interested in computing a block-encoding of the product of operators $V_n V_{n-1} \dots V_1$ given the access of the block-encodings of each $V_k$. The compession gadget is a way to multiply the $n$ block-encodings without requiring $n$ ancillary registers: It compresses it to one extra register of size $\lceil \log_2(n+1) \rceil$. The idea behind the Compression Gadget is to use an ancillae register name "counter" to identify successful application of each $V_i$, a.k.a. when the block-encoding's ancilla register is in the $0$ state. The Compression Gadget trick also allows to reduce the number of controls while using amplitude ampification, by using the the "counter" instead of the block-encoding's ancilla registers.
Recap on the Block-Encoding¶
The idea behind the block-encoding is to introduce the ancillae qubits to represent a non-unitary operator $V$ as a unitary matrix $U=BE(V)$ embedded into a large matrix. So, on a high level, the block encoding is a matrix of the form $$ BE(V) = \begin{pmatrix} V & * \\ * & * \end{pmatrix}. $$
If we apply a single block-encoding operator $BE(V)$ to some quantum state $|{\psi}\rangle= \begin{pmatrix} x \\ * \end{pmatrix}$, we obtain the operator $V$ applied to the $x$ and something that we are not interested in (aka. "garbage"). Usually this something is represented by an orthogonal state $|{\perp}\rangle$. $$ BE(V)|{0}\rangle|{\psi}\rangle = \begin{pmatrix} V & * \\ * & * \end{pmatrix} \begin{pmatrix} x \\ * \end{pmatrix} = \begin{pmatrix} Vx \\ * \end{pmatrix} = |{0}\rangle|{V \psi}\rangle + |{\perp}\rangle $$ If we measure out the ancilla qubit(s) in the zero-state, we find a new state $V |{\psi}\rangle$ (up to some normalization factor).
%load_ext autoreload
%autoreload 2
from psiqworkbench import Qubrick, QPU, Qubits
from psiqworkbench.qubricks import NaiveAdd
from psiqworkbench.utils.numpy_utils import reverse_numpy_op
import psiqworkbench.qubricks as qbk
import numpy as np
from workbench_algorithms.utils import (
PauliMask,
PauliSum,
pauli_sum_to_numpy,
PowerCompressionGadgetStrategy,
ListOfBlockEncodingsCompressionGadget
)
from workbench_algorithms import (
CompressionGadget,
PrepareNaive,
SelectNaive,
LCU
)
import random
The $HAM_1$ and $HAM_2$ represent the operators we want to block encode.
HAM1 = PauliSum(
[1, PauliMask(1, 0)],
[2, PauliMask(0, 1)],
)
HAM2 = PauliSum(
[0.1, PauliMask(1, 0)],
[0.9, PauliMask(0, 1)],
)
# represent HAM1 and HAM2 as block encodings
lst_ham = [HAM1, HAM2]
idx_stop = len(lst_ham)
lst_qbk_hams = [0] * idx_stop
for idx in range(idx_stop):
prep = PrepareNaive(lst_ham[idx].get_coefficients())
select = SelectNaive()
lst_qbk_hams[idx] = LCU(prep, select)
Naive Product of Block-Encodings¶
First, we explore the product of two block-encoded operators in the naive way: we introduce the separate ancillae registers for $HAM_1$ and $HAM_2$ to flag their zero subspaces.
num_system_qubits = 1
num_be_anc_qubits = idx_stop
total_qubits = num_be_anc_qubits + num_system_qubits
# prepare an arbitrary initial state.
initial_state_np = [random.random() for _ in range(1 << num_system_qubits)]
initial_state_np /= np.linalg.norm(initial_state_np)
initial_state = np.kron(np.eye(1, 1 << (total_qubits - num_system_qubits)), initial_state_np)[0]
def apply_naive_be(hamiltonians, lcus):
"""Apply the sequesnce of operators HAM1, HAM2 and return the probability of a successfull application."""
qc = QPU()
qc.reset(total_qubits)
system_reg = Qubits(num_system_qubits, "system_reg", qc)
be_anc_reg = Qubits(num_be_anc_qubits, "be_anc_reg", qc)
qc.push_state(initial_state)
for ind in range(len(hamiltonians)):
lcus[ind].compute(system_reg, be_anc_reg[ind], hamiltonians[ind])
total_prob = 1
for ind in range(len(hamiltonians)):
total_prob *= be_anc_reg[ind].peek_read_probability(0)
qc.draw()
return total_prob
total_prob = apply_naive_be(lst_ham, lst_qbk_hams)
print(f"Probability of applying block-encodings is {total_prob}")
Probability of applying block-encodings is 0.45555555555555555
Product of Block-Encodings with Compression Gadget¶
Now, we apply the same $HAM1$ and $HAM2$ but with an extra counter register. The counter register starts with the number of expected block encodings to be applied to the quantum state and is being decremented upon each application of the operator $BE(V_i)$. We decrement the value in the counter register conditioned on the block-encoding ancillae qubit(s) being in the $0$ state. Note that we use the same block-encoding ancillae qubits for both $BE(HAM1)$ and $BE(HAM2)$.
num_system_qubits = 1
num_be_anc_qubits = 1
num_counter_qubits = int(np.ceil(np.log2(idx_stop))) + 1
total_qubits = num_system_qubits + num_be_anc_qubits + num_counter_qubits
# initialize a QPU instance
qc = QPU()
qc.reset(total_qubits)
system_reg = Qubits(num_system_qubits, "system_reg", qc)
be_anc_reg = Qubits(num_be_anc_qubits, "be_anc_reg", qc)
counter_reg = Qubits(num_counter_qubits, "counter_reg", qc)
# push an arbitrary state to the quantum circuit
initial_state = np.kron(np.eye(1, 1 << (total_qubits - num_system_qubits)), initial_state_np)[0]
qc.push_state(initial_state)
cg_strat = ListOfBlockEncodingsCompressionGadget(lst_qbk_hams, lst_ham)
cg = CompressionGadget(cg_strat)
cg.compute(system_reg, be_anc_reg, idx_stop, counter=counter_reg)
counter = cg.get_result_qreg()
qc.draw()
prob = counter.peek_read_probability(0)
print(f"Probability of applying block-encodings is {prob}")
Probability of applying block-encodings is 0.45555555555555555
We have successfully applied the block-encoding of product $HAM_2 \cdot HAM_1$.
Although from this example it might not be clear how a compression gadget can help, but imagine a situation where we want to find the product of the $1024$ block encodings. In naive case we need at least (assuming each block encoding usses a single ancillae qubit) $1024$ ancillae qubits. If we use the compression gadget and reuse the block-encoding ancillae qubits, then we need as many as $\log_2(1024) = 10$ qubits for the counter register and the largest number of the block-encoding ancillae qubits among all ancillaes for the block encodings.