Verifying block encoding by computing inner products

Question

Assume that we know each matrix element $A_{ij}$ of a $n$-qubit matrix $A$, and we are given an $(n+m)$-qubit unitary $U_A$ that we would like to verify is a $(1,m)$-block encoding of $A$. To do this, we need to check that $$\langle 0^m, i | U_A |0^m,j\rangle = \langle i | A | j \rangle = A_{ij}.$$

Now, we can easily prepare the state $U_A|0^m, j\rangle$, but as I understand, it is impossible to design a quantum circuit that computes the inner product of the states, so we cannot take the inner product with $\langle 0^m, i|$, we can only compute the magnitude of the inner product (with, e.g., the SWAP test). So, how can block encoding actually be verified, since it seems like for all we know each entry in the top-left block of $U_A$ has the right magnitude but entirely the wrong phase, leading to a block encoded matrix $A'$ which is far away from $A$.

What I do know, is that if we prepare $U_A|0^m, j\rangle$, measure the first register, and post-select on on $0^m$ as the outcome, the resulting state on the second register is $\propto \sum_i A_{ij}|i\rangle$. I still don't clearly see how this can be used to verify the matrix entries.

Answer 1

You can use Hadamard test for this task.

Assume that you want to estimate the value of $A_{ij}$, then you can swap $i$ and $j$ columns then use Hadamard test to estimate $\langle j| U_A |j \rangle$. The Hadamard test is able to estimate the real and imaginary parts in two separate runs.

The following code demonstrates how to do that in Qiskit.

# i and j in binary
bin_i = bin(i)[2:].zfill(num_qubits)
bin_j = bin(j)[2:].zfill(num_qubits)
h_circ = QuantumCircuit(num_qubits + 1, 1)
<j|U|j>
for index, bit in enumerate(bin_j):
    if bit == '1':
        h_circ.x(num_qubits - index)
h_circ.barrier()
h_circ.h(0)
Set _imaginary = True to estimate the imaginary part
if _imaginary:
    h_circ.sdg(0)
h_circ.barrier()
SWAP columns i, j
for m in range(num_qubits):
    if bin_i[m] != bin_j[m]:
        h_circ.cx(0, num_qubits - m)
u_circ is the quantum circuits that implemnets
h_circ.append(u_circ.to_gate(label='     $U_A$     ').control(1), range(num_qubits + 1))
h_circ.barrier()
h_circ.h(0)
h_circ.measure(0, 0)

The circuit should look like below for $i = 2$ and $j = 3$