Is there any (really) quantum procedure that's an algorithm and not a Las Vegas algorithm?












2














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.










share|improve this question




















  • 1




    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.
    – The Vee
    Dec 20 at 8:04








  • 2




    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.
    – The Vee
    Dec 20 at 8:13












  • 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.
    – Nicholas Pipitone
    Dec 20 at 13:31


















2














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.










share|improve this question




















  • 1




    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.
    – The Vee
    Dec 20 at 8:04








  • 2




    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.
    – The Vee
    Dec 20 at 8:13












  • 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.
    – Nicholas Pipitone
    Dec 20 at 13:31
















2












2








2


1





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.










share|improve this question















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.







algorithm grovers-algorithm






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Dec 19 at 20:26

























asked Dec 19 at 20:20









R. Chopin

41210




41210








  • 1




    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.
    – The Vee
    Dec 20 at 8:04








  • 2




    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.
    – The Vee
    Dec 20 at 8:13












  • 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.
    – Nicholas Pipitone
    Dec 20 at 13:31
















  • 1




    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.
    – The Vee
    Dec 20 at 8:04








  • 2




    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.
    – The Vee
    Dec 20 at 8:13












  • 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.
    – Nicholas Pipitone
    Dec 20 at 13:31










1




1




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.
– The Vee
Dec 20 at 8:04






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.
– The Vee
Dec 20 at 8:04






2




2




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.
– The Vee
Dec 20 at 8:13






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.
– The Vee
Dec 20 at 8:13














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.
– Nicholas Pipitone
Dec 20 at 13:31






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.
– Nicholas Pipitone
Dec 20 at 13:31












3 Answers
3






active

oldest

votes


















9














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.






share|improve this answer








New contributor




Guang Hao Low is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.


















  • 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?
    – R. Chopin
    Dec 19 at 23:54










  • 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.
    – Guang Hao Low
    Dec 20 at 0:07



















7















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.






share|improve this answer





















  • 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.
    – R. Chopin
    Dec 19 at 23:54



















4














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.






share|improve this answer





















    Your Answer





    StackExchange.ifUsing("editor", function () {
    return StackExchange.using("mathjaxEditing", function () {
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    });
    });
    }, "mathjax-editing");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "694"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: false,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: null,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f5020%2fis-there-any-really-quantum-procedure-thats-an-algorithm-and-not-a-las-vegas%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    3 Answers
    3






    active

    oldest

    votes








    3 Answers
    3






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    9














    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.






    share|improve this answer








    New contributor




    Guang Hao Low is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.


















    • 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?
      – R. Chopin
      Dec 19 at 23:54










    • 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.
      – Guang Hao Low
      Dec 20 at 0:07
















    9














    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.






    share|improve this answer








    New contributor




    Guang Hao Low is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.


















    • 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?
      – R. Chopin
      Dec 19 at 23:54










    • 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.
      – Guang Hao Low
      Dec 20 at 0:07














    9












    9








    9






    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.






    share|improve this answer








    New contributor




    Guang Hao Low is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    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.







    share|improve this answer








    New contributor




    Guang Hao Low is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    share|improve this answer



    share|improve this answer






    New contributor




    Guang Hao Low is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.









    answered Dec 19 at 20:45









    Guang Hao Low

    912




    912




    New contributor




    Guang Hao Low is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.





    New contributor





    Guang Hao Low is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.






    Guang Hao Low is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.












    • 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?
      – R. Chopin
      Dec 19 at 23:54










    • 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.
      – Guang Hao Low
      Dec 20 at 0:07


















    • 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?
      – R. Chopin
      Dec 19 at 23:54










    • 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.
      – Guang Hao Low
      Dec 20 at 0:07
















    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?
    – R. Chopin
    Dec 19 at 23:54




    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?
    – R. Chopin
    Dec 19 at 23:54












    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.
    – Guang Hao Low
    Dec 20 at 0:07




    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.
    – Guang Hao Low
    Dec 20 at 0:07













    7















    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.






    share|improve this answer





















    • 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.
      – R. Chopin
      Dec 19 at 23:54
















    7















    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.






    share|improve this answer





















    • 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.
      – R. Chopin
      Dec 19 at 23:54














    7












    7








    7







    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.






    share|improve this answer













    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.







    share|improve this answer












    share|improve this answer



    share|improve this answer










    answered Dec 19 at 20:52









    Niel de Beaudrap

    5,4751932




    5,4751932












    • 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.
      – R. Chopin
      Dec 19 at 23:54


















    • 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.
      – R. Chopin
      Dec 19 at 23:54
















    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.
    – R. Chopin
    Dec 19 at 23:54




    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.
    – R. Chopin
    Dec 19 at 23:54











    4














    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.






    share|improve this answer


























      4














      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.






      share|improve this answer
























        4












        4








        4






        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.






        share|improve this answer












        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.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Dec 19 at 21:02









        cnada

        1,809211




        1,809211






























            draft saved

            draft discarded




















































            Thanks for contributing an answer to Quantum Computing Stack Exchange!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            Use MathJax to format equations. MathJax reference.


            To learn more, see our tips on writing great answers.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f5020%2fis-there-any-really-quantum-procedure-thats-an-algorithm-and-not-a-las-vegas%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            數位音樂下載

            When can things happen in Etherscan, such as the picture below?

            格利澤436b