# Quantum Algorithm to Determine if two vectors are orthogonal

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:

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.

• Do you assume a single copy of both $|\phi\rangle$ and $|\psi\rangle$? Mar 6, 2023 at 15:23
• @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. Mar 6, 2023 at 15:44
• @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. Mar 6, 2023 at 17:24
• 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 Mar 6, 2023 at 17:55