3
$\begingroup$

Let me take Grover's algorithm as an example. In most cases, Grover's algorithm is able to yield with a high probability the desired term of the superposition. When the superposition has more than 4 terms, there's a small chance we will not obtain the desired term of the superposition, in which case we can repeat the procedure and measure it again, until we really get the desired result.

Although the probability of not getting the desired result decreases exponentially, it is technically not guaranteed that one will ever get the desired measurement. Therefore, we cannot prove that Grover's algorithm is an algorithm because we cannot prove it terminates with the correct answer in a finite number of steps. (Otherwise, what part of the definition of "algorithm" I'm missing here?)

We can however define Grover's algorithm as a Las Vegas algorithm because if we do not measure the desired result, we could produce a "failure" result, satisfying therefore the definition of "Las Vegas algorithm".

Surely a quantum computer is able to calculate everything a classical computer can, so quantum computers can execute algorithms in the formal sense of the word. But is there an algorithm (not a Las Vegas algorithm) that uses true quantum features like superpositions and entanglement always producing the right answer in a finite number of steps and is not a Las Vegas algorithm? That's what I'm after. I appreciate any light on this direction.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Btw, Grover's algorithm can be also made exact by a small modification to prevent the "overshoot" in the last iteration. A quick search on Google gives me researchgate.net/publication/…, but there will be more. $\endgroup$
    – The Vee
    Dec 20, 2018 at 8:04
  • 2
    $\begingroup$ Of course it needs to be added that while the question is interesting from a theoretical / CS point of view, exact algorithms are no better than probabilistic ones in view of actual quantum computing. Once noise is counted in no amount of error correction retains unit success probability. $\endgroup$
    – The Vee
    Dec 20, 2018 at 8:13
  • 2
    $\begingroup$ Almost every cryptographic algorithm has a "But this won't work 1/2^256th of the time" attached to it, usually in the sense of assuming that it's impossible for two different inputs have the same hash. That doesn't mean it's "Not an algorithm", just because it has an exponentially low chance of failing. $\endgroup$
    – Nicholas Pipitone
    Dec 20, 2018 at 13:31

3 Answers 3

Reset to default
9
$\begingroup$

It sounds like you're looking for algorithms that succeed deterministically with probability 1, instead of probabilistic algorithms that succeed with probability bounded from a 1/2 by a finite amount, say 2/3.

Exact is the keyword for deterministic quantum algorithms, such as in this paper Exact quantum algorithms have advantage for almost all Boolean functions by Andris Ambainis, Jozef Gruska, Shenggen Zheng that answers your question in the affirmative.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Pretty nice reference. Reading the abstract it seems they have designed quantum boolean algorithms that are exact and faster than all classical counterparts except for AND? $\endgroup$
    – R. Chopin
    Dec 19, 2018 at 23:54
  • 1
    $\begingroup$ Yes, but keep in mind this that this paper uses a certain standard query model, where the cost function is number of accesses to a unitary black-box circuit that returns the j-th bit if you feed it an index j. This must be distinguished from the gate model that counts the number of primitive quantum gates. $\endgroup$
    – Guang Hao Low
    Dec 20, 2018 at 0:07
8
$\begingroup$

Although the probability of not getting the desired result decreases exponentially, it is technically not guaranteed that one will ever get the desired measurement. Therefore, we cannot prove that Grover's algorithm is an algorithm because we cannot prove it terminates with the correct answer in a finite number of steps. (Otherwise, what part of the definition of "algorithm" I'm missing here?)

It is important that an 'algorithm' terminates, but it is possible to consider slightly more flexible final conditions than you are considering when it does terminate. This is true of classical algorithms as well as quantum algorithms.

A Las Vegas algorithm is one which can 'succeed' or 'fail', and which produces a correct result whenever it 'succeeds' (so that it is meaningful to say that it has succeeded). We look for the probability of failure to be low, ideally — and this can be achieved in principle by trying again if you don't succeed (though in some cases you may end up trying many times).

This idea is taken seriously enough that there is a Las Vegas version of the complexity class P, known as ZPP. (It does not do to take complexity class names too seriously, but the acronym stands for "zero error probabilistic polynomial-time", as it is the class of decision problems solvable in polynomial time, using randomness, and without error — allowing however for a bounded probability of failing to produce a YES/NO answer at all.) This is a class between P and BPP.

There is an analogous class, ZQP, of problems solvable with an idealised quantum computer in polynomial time with zero error, which happens to contain integer factorisation (due to a combination of Shor's algorithm, the fact that verifying integer multiplication is in P, and the fact that primality testing is in ZPP and indeed also in P). These of course are analogous to 'Las Vegas' algorithms in the sense that they are zero error (though 'Las Vegas' would usually only be used for classical randomised algorithms) — and in particular, they are indeed algorithms.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the nice answer. So what I called Las Vegas algorithms should be called ZQP algorithms in the case of being a quantum algorithm. Okay. $\endgroup$
    – R. Chopin
    Dec 19, 2018 at 23:54
5
$\begingroup$

Firstly, I would say that when you embrace quantum computing, you are considering probabilistic programming and not deterministic if I may say so (so your definition of algorithm depends on the kind of programming/computing you are doing). It will still be an algorithm though because you create a circuit (which is what we call an algorithm in quantum computing with the circuit model). A quantum algorithm through its quantum operations change the quantum state of a circuit(and this is the definition of quantum computing). Briefly said, this is just a different kind of computing.

If you are looking for deterministic output though from a quantum algorithm, we can take quantum circuits for arithmetic operations like adder circuits. You have also the common quantum phase estimation in the case you input one eigenvector of the unitary operation of interest. In that case, it outputs the phase (approximately) associated with the eigenvector provided exactly.

Improve this answer
$\endgroup$

Your Answer

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

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