5
$\begingroup$

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?

$\endgroup$
4
  • 2
    $\begingroup$ Does this answer your question? What's an use case of the inner product between two qubits in a quantum algorithm? $\endgroup$ – glS Apr 24 at 15:34
  • 1
    $\begingroup$ This question asks for a quantum algorithm to compute the real and imaginary part of the inner product of two input states. The proposed duplicate asks about the use-cases for the inner product in quantum computing. They are not duplicates. $\endgroup$ – Adam Zalcman Apr 25 at 19:11
  • $\begingroup$ @AdamZalcman Although the above post didn't answer my question, it's still an interesting post worth noticing as I myself has recently developed a quantum machine learning algorithm which inevitably involves the inner product of two general quantum states. I don't mind my algorithm being hybrid quantum-classical, but my team believed there might be a way to implement it in a fully quantum way... $\endgroup$ – cwhsing Apr 27 at 6:04
  • $\begingroup$ Agreed. The other question is interesting and has some good answers. It just isn't a duplicate of your question and hence the latter should not be closed. BTW: I highly recommend digging into past questions on this site. Many are very interesting and have insightful answers. $\endgroup$ – Adam Zalcman Apr 27 at 16:47
5
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ I've conjectured that such a circuit/routines doesn't exist but don't know exactly how to prove it. Your proof is quite succinct and helpful! $\endgroup$ – cwhsing Apr 27 at 7:59
  • $\begingroup$ The only baffling thing remains is what states the CZ-based quantum circuit actually applies to. You mentioned that it also works for superpositions of computational basis states but doesn't work for general quantum states. Since arbitrary quantum state can be expressed as superposition of computational basis, does this imply that the states the quantum circuit works for are some special set of superposition states? $\endgroup$ – cwhsing Apr 27 at 8:46
  • $\begingroup$ You are correct in saying that every $n$-qubit quantum state can be written as a superposition of computational basis states. Consequently, the circuit does work for all quantum states. Its action on an arbitrary $n$-qubit state $|\psi\rangle$ can be obtained by expressing $|\psi\rangle$ in the computational basis and applying $(1)$ to every term. The action amounts to changing relative phase factors. Note that if $|\psi\rangle$ is a computational basis state then the action of the circuit is trivial (merely change in global phase). $\endgroup$ – Adam Zalcman Apr 27 at 16:33
  • $\begingroup$ The official answer finally came out: They did make it misleading. Please see github.com/Qiskit/qiskit/issues/1242 and github.com/Qiskit/qiskit-terra/issues/5649 $\endgroup$ – cwhsing May 26 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.