6

I've been searching for a quantum algorithm to compute the the inner product between two $n$-qubit quantum states, namely $\langle\phi|\psi\rangle$, which is in general a complex number.

One can get $|\langle\phi|\psi\rangle|^2$ through thte SWAP test for multiple qubits, but this is not really the inner product as the information of the real and imaginary parts are lost.

I came across this qiskit page, which claims that the task can be done by simply using CZ gates. I'm not sure if I am mistaken, but it seems to me that such a circuit works for computational basis states, but not for general quantum states. Could somebody help me confirm if this is actually the case?

If the above algorithm doesn't work for general quantum states, what algorithm would you suggest?

Adam Zalcman
  • 25,260
  • 3
  • 40
  • 95
cwhsing
  • 63
  • 4

1 Answers1

6

Suppose $\langle\phi|\psi\rangle = re^{i\theta}$. As you have noticed, if we have access to multiple copies of the state, then we can measure $r$ using the SWAP test. Now, consider the state $|\psi'\rangle = e^{-i\theta}|\psi\rangle$ and note that

$$ \langle\phi|\psi'\rangle = e^{-i\theta}\langle\phi|\psi\rangle = e^{-i\theta}re^{i\theta} = r. $$

Since $|\psi'\rangle$ and $|\psi\rangle$ differ only by the global phase, we see that a quantum circuit computing $re^{i\theta}$ would let us observe the global phase difference between $|\psi\rangle$ and $|\psi'\rangle$ which is unobservable. We conclude that such a quantum circuit does not exist. All we have observational access to is the magnitude of the inner product $\langle\phi|\psi\rangle$.


For two $n$-qubit computational basis states $|x\rangle$ and $|y\rangle$, the CZ-based quantum circuit computes

$$ (-1)^{x \cdot y}|x\rangle|y\rangle,\tag1 $$

where $x\cdot y=\sum_{i=1}^n x_iy_i$ is the inner product between binary vectors $x=(x_1,\dots,x_n)$ and $y=(y_1,\dots,y_n)$. The inner product $\cdot$ is defined in the vector space $\mathbb{Z}_2^n$ of binary strings on $n$ bits and is a different inner product than $\langle \,.|\,.\rangle$ defined in the Hilbert space.

Note that the circuit does work for states other than computational basis states by linear extension. In fact, its only action on a computational basis is to change the unobservable global phase, so it is only useful on states that are superpositions of computational basis states where its effect is to change the relative phases according to the $\mathbb{Z}_2^n$ inner product of the states.

In any case, the circuit does not compute $\langle\phi|\psi\rangle$.

Adam Zalcman
  • 25,260
  • 3
  • 40
  • 95