Inner product
Definiton and example
Supposedly, we are given two vector \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^{n}\), the inner product between them is defined as
\[ \braket{\mathbf{x}, \mathbf{y}} \triangleq \mathbf{x}^\top \mathbf{y} \triangleq \mathbf{y}^\top \mathbf{x} := \sum_{i=1}^{n}x_iy_i. \]For example, \(\mathbf{x} = \begin{bmatrix}1 & -2 & 3 & -4\end{bmatrix}^\top\), and \(\mathbf{y} = \begin{bmatrix}-3 & 2 & 0 & -2.3\end{bmatrix}^\top\), the inner product between \(\mathbf{x}\) and \(\mathbf{y}\) is
\[ \braket{\mathbf{x}, \mathbf{y}} = \sum_{i=1}^{4}x_iy_i = 1\cdot (-3) + (-2) \cdot 2 + 3 \cdot 0 + (-4)\cdot (-2.3) = 2.22. \]import numpy as np
x = np.array([1, -2, 3, -4])
y = np.array([-3, 2, 0, -2.3])
print("Inner product between x, y: {}".format(x @ y))
Click here to see the output
Inner product between x, y: 2.1999999999999993
Geometry intuition
What does the inner product between two vectors tell us? Well, to answer this question, let see the relation between the angle between two vectors and its innner product through the formula,
\[ \cos{\angle(\mathbf{x}, \mathbf{y})} = \frac{\braket{\mathbf{x}, \mathbf{y}}}{||\mathbf{x}||_2 ||\mathbf{y}||_2}. \]From the formula, we see that the angle between \(\mathbf{x}\), and \(\mathbf{y}\) can be determined through its inner product, which means the inner product tell us the spatial relationship between vector objects.
If \(\braket{\mathbf{x},\mathbf{y}} = 0\), which means \(\angle(\mathbf{x}, \mathbf{y}) = \pi/2 + k\pi\), \(k \in \mathbb{N}\). Therefore, \(\mathbf{x}\) and \(\mathbf{y}\) are orthogonal in this case. If their inner product is \(-1\), which means \(\mathbf{x} = -c\mathbf{y}\), with some positive scalar \(c\). On the other hand, if \(x\) and \(\mathbf{y}\) are same direction, i.e., \(\mathbf{x} = c\mathbf{y}\), then their inner product yeilds \(1\).
Quantum inner product
Idealization
Given \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^{N}\) We want to design a quantum circuit \(\mathcal{Q}\) such that \(\mathcal{Q}\) encode the inner product \(\braket{\mathbf{x}, \mathbf{y}}\) into the first coefficient of its quantum state \(\ket{\psi}\), i.e.,
\[ \mathcal{Q}: (\mathbf{x}, \mathbf{y}) \rightarrow \ket{\psi}_0. \]Supposedly, we are given quantum oracles \(\mathbf{U}_{\mathbf{A}}\), and \(\mathbf{U}_{\mathbf{B}}\), which are unitary matrices, such that
\[ \begin{aligned} \mathbf{U}_{\mathbf{A}}\ket{0}_{n} &= \ket{a},\\ \mathbf{U}_{\mathbf{B}}\ket{0}_{n} &= \ket{b}, \end{aligned} \]where \(\ket{a}, \ket{b}\) are quantum encoding representation of \(\mathbf{a}\), and \(\mathbf{b}\) respectively. Precisely speaking, given a classical vector \(\mathbf{x}\), one way to encode it into a quantum world is amplitude encoding which its coordinate values are scaled by its magnitude, i.e.,
\[ \ket{x} := \frac{\mathbf{x}}{||\mathbf{x}||_2}. \]To do not lost the generality, we assume \(N\) is the power of \(2\), and \(n = \log_2{N}\). Now we compute the inner product between quantum state \(\ket{a}\), and \(\ket{b}\) as
\[ \begin{aligned} \braket{a|b} &= \ket{a}^{*}\ket{b} \\ &= \left(\frac{\mathbf{a}}{||\mathbf{a}||_2}\right)^{*} \left(\frac{\mathbf{b}}{||\mathbf{b}||_2}\right) \\ &= \frac{\mathbf{a}^\top\mathbf{b}}{||\mathbf{a}||_2||\mathbf{b}||_2}. \end{aligned} \]Therefore the inner product between two quantum state \(\ket{a}\), and \(\ket{b}\) is proportional to the inner product of two vectors \(\mathbf{a}, \mathbf{b}\). In particular, the equation below holds
\[ \braket{\mathbf{a}, \mathbf{b}} = ||\mathbf{a}||_2 ||\mathbf{b}||_2 \braket{a|b}. \]Thus, we will design a quantum algorithm to comptue \(\braket{a|b}\), then classically multiplying with norms to get the classical result. Notice that, if we consider the circuit \(\mathcal{Q}\) as
\[ \mathcal{Q}: \ket{0}_n \rightarrow \ket{\psi} := \mathbf{U}_{\mathbf{A}}^{\dagger}\mathbf{U}_\mathbf{B}\ket{0}_n, \]the first entry of \(\ket{\psi}\) is the quantum inner product. Now prove it! Let \(\ket{\psi} = \begin{bmatrix}\gamma_0, \gamma_1, \dots, \gamma_N\end{bmatrix}^{*}\), we need to prove
\[ \gamma_0 = \braket{a|b}. \]Consider the inner product between \(\ket{0}_n\) and \(\ket{\psi}\), we have
\[ \braket{0|\psi} = \begin{bmatrix}1 & 0 & \cdots & 0\end{bmatrix}\begin{bmatrix}\gamma_0 \\ \gamma_1 \\ \vdots \\\gamma_N\end{bmatrix} = \gamma_0. \]On the other side, we can use \(\mathbf{U}_{\mathbf{A}}^{\dagger}\mathbf{U}_\mathbf{B}\ket{0}_n\) as representation for \(\ket{\psi}\), then
\[ \begin{aligned} \braket{0|\psi} &= \bra{0}_n\mathbf{U}_{\mathbf{A}}^\dagger\mathbf{U}_{\mathbf{B}}\ket{0}_n \\ &= \left(\bra{0}_n\mathbf{U}_{\mathbf{A}}^{\dagger}\right)\left(\mathbf{U}_{\mathbf{B}}\ket{0}_n\right) \\ &= \left(\mathbf{U}_{\mathbf{A}}\ket{0}_n\right)^\dagger\left(\mathbf{U}_{\mathbf{B}}\ket{0}_n\right) \\ &= \ket{a}^\dagger \ket{b} \\ &= \braket{a|b}. \end{aligned} \]Therefore, \(\gamma_0 = \braket{a|b}\).
Running time analysis
The cost of this quantum algorithm depends on how efficiency we construct the oracles \(\mathbf{U}_\mathbf{a}\), and \(\mathbf{U}_{\mathbf{b}}\). Assuming efficient methods for encoding classical data 1, it costs
\[ \mathcal{O}(\textrm{poly}\log{N}), \]which is exponential speed up compare to the classical approach for computing the inner product.
Practical implementation
Installation and predefined functions
Package installment
!pip install qiskit==1.4.2 -q
!pip install qiskit_aer -q
!pip install qiskit_ibm_runtime -q
Import packages
import numpy as np
from qiskit import QuantumCircuit, QuantumRegister
from qiskit_aer import AerSimulator
from qiskit.circuit.library import UnitaryGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit_ibm_runtime import QiskitRuntimeService, Session, SamplerV2 as Sampler
Predefined functions/classes
MEAN = 0
STD = 1.5
Aerbackend = AerSimulator()
def generate_random_vector(size: int):
return np.random.normal(loc=MEAN, scale=STD, size=size)
class QuantumInnerProduct:
def __init__(self):
pass
def _padding(self, x: np.ndarray):
N = len(x)
n = np.log2(N)
if int(n) == n:
return x
K = 2**(int(n)+1)-N
zero_array = np.zeros(K)
return np.append(x, [zero_array])
def _prepare_unitary_matrix(self, x: np.ndarray):
x_norm = np.linalg.norm(x)
fist_column = x / x_norm
U_x = np.zeros((len(x), len(x)))
U_x[:, 0] = fist_column
for i in range(1, len(x)):
v = np.eye(len(x))[i]
for j in range(i):
v -= (np.dot(U_x[:, j], v) * U_x[:, j]).real
v /= np.linalg.norm(v)
U_x[:, i] = v
return U_x
def build_quantumcircuit(self, a: np.ndarray, b: np.ndarray):
M = len(a)
N = len(b)
assert M == N, "The input dimension is not match"
a_padded = self._padding(a)
b_padded = self._padding(b)
U_a = self._prepare_unitary_matrix(a_padded)
U_b = self._prepare_unitary_matrix(b_padded)
Ub_gate = UnitaryGate(U_b, label="Ub")
Ua_dagger_gate = UnitaryGate(U_a.T.conj(), label="UaD")
n = np.log2(a.shape[0])
reg = QuantumRegister(n)
qc = QuantumCircuit(reg)
qc.append(Ub_gate, reg)
qc.append(Ua_dagger_gate, reg)
return qc
Input
N = 8
a = generate_random_vector(size=N)
b = generate_random_vector(size=N)
print("a = ", a)
print("b = ", b)
c_res = a @ b
print("Inner product: a@b: ", c_res)
Click here to see the output.
a = [ 0.77809837 -1.05933594 4.02862416 2.28307468 -2.10256477 0.01756594
-0.36928294 -1.15087132]
b = [ 0.61185187 0.35410639 2.98870722 2.4536637 -1.69838534 -2.42383467
-0.45221679 0.29014932]
Inner product: a@b: 21.104698520674955
Note that, since \(\mathbf{a}, \mathbf{b}\) were generated by random normal distribution, the inner product between them is not deterministic every time you run the code. So don’t be suprise if you get different result.
Initialize the quantum algorithm instance
qa = QuantumInnerProduct()
Build quantum circuit
qc = qa.build_quantumcircuit(a=a, b=b)
print(qc.draw())
Click here to see the output
┌─────┐┌──────┐
q1_0: ┤0 ├┤0 ├
│ ││ │
q1_1: ┤1 Ub ├┤1 UaD ├
│ ││ │
q1_2: ┤2 ├┤2 ├
└─────┘└──────┘
State vector simulation
Run the quantum circuit on the simulator using Aerbackend
qc.save_statevector()
job = Aerbackend.run(qc)
result = job.result()
statevector = result.get_statevector()
print("Statevector:", statevector)
Click here to see the output.
Statevector: Statevector([ 0.16734804+0.j, -0.44719024+0.j, 0.52738211+0.j,
-0.46628378+0.j, -0.02708338+0.j, -0.01439923+0.j,
-0.4164406 +0.j, -0.31953004+0.j],
dims=(2, 2, 2))
Readout the first element in statevector and recover to the classical inner product
scaled_res = statevector.data[0].real
print("The quantum inner product: gamma0 = ", scaled_res)
q_res = scaled_res*np.linalg.norm(a)*np.linalg.norm(b)
print("The recovery inner product = ", q_res)
Click here to see the output.
The quantum inner product: gamma0 = 0.16734804111984383
The recovery inner product = 3.0483014861522353
q_res = scaled_res*np.linalg.norm(a)*np.linalg.norm(b)
print(q_res)
Click here to see the output.
3.0483014861522353
Comparision to the classical inner product
print("Quantum inner product: {}".format(q_res))
print("Classical inner product: {}".format(inner_product))
print("Difference: {}".format(q_res - inner_product))
Click here to see the output
Quantum inner product: 3.0483014861522353
Classical inner product: 3.0483014861522353
Difference: 0.0
Run the experiment on IBM quantum devices
service = QiskitRuntimeService()
qbackend = service.backend('ibmq_qasm_simulator')
print(qbackend)
Click here to see the output
<IBMBackend('ibmq_qasm_simulator')>
I would like to use actual quantum devices, but I have waited for a couple of decades in the queue. So I will recommend you to use the simulator for now. But if have time, I will try to run on the real quantum devices by using the command below instead.
qbackend = service.least_busy(operational=True, simulator=False)
#OR
qbackend = service.backend("ibm_fez") # replace ibm_fez by your favor by checking your IBM quantum resources
Next we need to transpile the circuit to the target backend. The transpilation is a process of converting a quantum circuit into a form that can be executed on a specific quantum computer. This involves optimizing the circuit for the target architecture, which may have constraints on the number of qubits, connectivity, and gate types.
pm = generate_preset_pass_manager(backend=qbackend, optimization_level=1)
Now we can build the quantum circuit and run it on the target backend. The build_quantumcircuit method creates a quantum circuit that implements the quantum inner product algorithm. The measure_all method adds measurement operations to all qubits in the circuit, allowing us to read out the final state of the qubits after execution.
qc = qa.build_quantumcircuit(a=a, b=b)
qc.measure_all()
print(qc)
Click here to see the output
┌─────┐┌──────┐ ░ ┌─┐
q2_0: ┤0 ├┤0 ├─░─┤M├──────
│ ││ │ ░ └╥┘┌─┐
q2_1: ┤1 Ub ├┤1 UaD ├─░──╫─┤M├───
│ ││ │ ░ ║ └╥┘┌─┐
q2_2: ┤2 ├┤2 ├─░──╫──╫─┤M├
└─────┘└──────┘ ░ ║ ║ └╥┘
meas: 3/═══════════════════╩══╩══╩═
0 1 2
We use pm object to transpile the circuit for the target backend. The run method of the pm object executes the circuit on the target backend, and we can use the Session class to manage the execution context.
isa_circuit = pm.run(qc)
print(f">>> Circuit ops (ISA): {isa_circuit.count_ops()}")
Click here to see the output
>>> Circuit ops (ISA): OrderedDict([('rz', 120), ('sx', 116), ('p', 50), ('cx', 40), ('measure', 3), ('barrier', 1)])
We run the circuit on the target backend using the Session class. The Sampler class is used to sample the results of the circuit execution. The run method of the Sampler class executes the circuit and returns a job object, which contains the results of the execution.
with Session(backend=qbackend) as session:
sampler = Sampler(mode=session)
job = sampler.run([isa_circuit], shots=int(1e6))
print(f"Sampler job ID: {job.job_id()}")
Click here to see the output
Sampler job ID: cznngqtp3xeg008hgzy0
Retrieve the results of the execution using the result method of the job object. The result method returns a list of counts, which represent the measurement results of the qubits in the circuit.
result = job.result()
dict_count = result[0].data.meas.get_counts()
print(dict_count)
Click here to see the output
{'000': 625544, '101': 240345, '100': 26523, '011': 27559, '111': 18370, '001': 53609, '010': 1167, '110': 6883}
We get the estimate probability of the obtaining the state \(\ket{0\dots0}\) as
prob = dict_count['000']/sum(dict_count.values())
print("Probability of the |0...0> is {}".format(prob))
Click here to see the output
Probability of the |0...0> is 0.625544
Now we can compute the absolute scaled of the first coefficient of the quantum state, which is the inner product between \(\mathbf{a}\), and \(\mathbf{b}\). The result is scaled by the norms of \(\mathbf{a}\), and \(\mathbf{b}\) as well.
abs_value = np.sqrt(prob)
print("The absolute scaled value of the first coordinate is {}".format(abs_value))
Click here to see the output
The absolute scaled value of the first coordinate is 0.7909133960175412
Finally, we can compute the inner product between \(\mathbf{a}\), and \(\mathbf{b}\) as
q_res = abs_value*np.linalg.norm(a)*np.linalg.norm(b)
print("The quantum inner product: {}".format(q_res))
Click here to see the output
The quantum inner product: 21.101120915202
Comparision
Now we compare three results: classical inner product, quantum inner product running on AerSimulator, and quantum inner product running on IBM quantum devices.
print("Quantum inner product running on IBM's {}: {}".format(qbackend.name, qibm_res))
print("Quantum inner product using Aer's simulator: {}".format(q_res))
print("Classical inner product: {}".format(c_res))
Click here to see the output
Quantum inner product running on IBM's ibmq_qasm_simulator: 21.101120915202
Quantum inner product using Aer's simulator: 21.104698520674955
Classical inner product: 21.104698520674955