Let's consider the Deutsch Jozsa algorithm, I understand that the superposition principle in quantum mechanics, helps us design circuits which would give answers in one single query. But then I would expect the query complexity to be $O(1)$, but it is told to be $O(n)$ which I don't understand?

The next question I have is, although the quantum circuits ideally give answers in a single query, the probabilistic nature of QM, dictates us to perform measurements multiple times for a more accurate picture, so why do we not consider that in query complexity?

  • 1
    $\begingroup$ Quantum advantage is the ability to perform a particular task on a quantum computer faster than the classical computer counter part using the best available algorithms. For instance, we believe that factoring is very hard, and there is no efficient classical algorithm to solve it efficiently. A lot of smart people have tried, but failed to come up with an efficient classical method. But on a quantum computer, it can be proven to have an efficient solution. Hence, factoring large number on a quantum computer give you a quantum advantage. $\endgroup$
    – KAJ226
    Sep 22 '21 at 4:16
  • 3
    $\begingroup$ In regard to measurement, note that if the the state of your solution belongs in a particular computational basis then you don't need to perform measurements multiple times... For instance, if you have the state $|\psi \rangle = |1100\rangle$ then it only takes one measurement to read out this exact state, assuming that you have a perfect quantum computer, of course. $\endgroup$
    – KAJ226
    Sep 22 '21 at 4:17
  • 1
    $\begingroup$ titular question and question body don't quite match. Are you asking the general question in the title, or the more specific ones in the body? Note that each post should contain a single, laser-focused question. You can open different posts to ask different things $\endgroup$
    – glS
    Sep 22 '21 at 8:38

As KAJ226 mentioned in the comments, "quantum advantage" refers to the ability of running an algorithm using a quantum computer that would have taken a dereasonable time on a classical one.

Generally speaking, we often talk about quantum advantage when using a quantum computer, or having access to a quantum oracle in the case of the Deutsch-Jozsa algorithm, reduces exponentially the complexity of the algorithm by an exponential factor. For instance, if you want to solve the Deutsch-Jozsa problem with a probability of success equal to $1$, you have to perform $\mathcal{O}\left(2^n\right)$ queries on $f$. On the other hand, you only need a single query on $f$ implemented as a quantum oracle to solve the problem. Thus the complexity of this quantum algorithm is $\mathcal{O}(1)$. Of course, this assumes:

  • the implementation of $f$ as a quantum oracle is done in time $\mathcal{O}(1)$;
  • the $H^{\otimes n}$ gate is built by applying $n$ $H$ gates in parallel. Were you to have to apply them subsequently, the algorithm now runs in $\mathcal{O}(n)$.

In the case of the Deutsch-Jozsa algorithm, the complexity is thus $\mathcal{O}(1)$. Note that quite often, it is not possible to design a quantum circuits that gives us the answer we are looking for in a single query. Deutsch-Jozsa is quite a special case when a single query is enough to solve the problem, but Simon's algorithm, for instance, requires us to run $n-1$ queries on the quantum oracle.

Finally, note that everything above assumes that the qubits we are working with are perfect: we didn't consider noise or decoherence. When designin a quantum algorithm, it is common to assume that it will run in such a perfect world. The goal is thus only to maximize the probability of your measurements being correct. Taking a few examples:

  • the Deutsch-Jozsa algorithm succeeds with probability $1$, since we measure $|0\rangle^{\otimes n}$ with probability $1$ if $f$ is constant and with probability $0$ is $f$ is balanced
  • every measurement performed during Simon's algorithm yields a vector $y$ such that $y\cdot s = 0$ with probability $1$
  • Grover's algorithm yields a valid state with almost certainty. You thus have to perform a classical postprocessing to check whether this state is indeed valid.

All in all, as long as you can assume that your quantum computer is perfect, the quantum algorithms are designed so that the probability of measuring what we are looking for is $1$, or very close to it.


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.