I have seen some sources use a quantum algorithm to estimate inner products between two states. The algorithm used from this answer is shown here:

enter image description here

But this algorithm has limitations; if the inner product is small (less than $\frac{1}{3}$), then the probability of measuring 1 is too low. This can be an issue for vectors that are not orthogonal, but can’t be tested otherwise in a polynomial number of steps.

Is there another quantum algorithm to determine the correct inner product, maybe similar to methods used in QPE, that solve for $N$ times the inner product in binary?

Or is there an algorithm that just tests if two states are orthogonal with accuracy greater than $\frac{2}{3}$?

And of course, we can also introduce an error term in the complexity.

  • $\begingroup$ Do you assume a single copy of both $|\phi\rangle$ and $|\psi\rangle$? $\endgroup$
    – Tristan Nemoz
    Mar 6, 2023 at 15:23
  • $\begingroup$ @TristanNemoz Oh, I haven’t considered that. I believe that we could simply run the algorithm a quasipolynomial number of times (some term that’s a bit long to write here) and watch out for a nonzero output value. I think it may be more interesting to assume only one copy of each term. $\endgroup$
    – Loic Stoic
    Mar 6, 2023 at 15:44
  • $\begingroup$ @TristanNemoz Oh, I miscalculated a little bit. We have to call the the original algorithm $\Omega \left ( \frac{log(1)-log(3)}{log \left ( 2^{2x} - 1 \right ) - log \left ( 2^{2x} \right )} \right )$ where $x$ is the number of qubits in each state. I think this is super exponential. Thus I retract my previous statement; we can use copies of the two states. $\endgroup$
    – Loic Stoic
    Mar 6, 2023 at 17:24
  • $\begingroup$ This is equal to $\Omega\left(2^{2n}\right)$, so this is not super exponential. I think that the SWAP test is optimal to determine the scalar product between two states, but someone should confirm this. If that's the case, I think your best guess is simply to run the SWAP test a large number of times and to compute the expectation of the associated random variable. You will get $\frac12+\frac12\left|\langle\psi|\phi\rangle\right|^2$ in average, which converges in $O\left(\frac{1}{\sqrt{p}}\right)$, with $p$ being the number of times you run the algorithm $\endgroup$
    – Tristan Nemoz
    Mar 6, 2023 at 17:55


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.