Is there any (really) quantum procedure that's an algorithm and not a Las Vegas algorithm?
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
add a comment |
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
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
add a comment |
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
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
algorithm grovers-algorithm
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
add a comment |
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
add a comment |
3 Answers
3
active
oldest
votes
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.
New contributor
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
add a comment |
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.
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
add a comment |
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.
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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.
New contributor
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
add a comment |
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.
New contributor
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
add a comment |
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.
New contributor
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.
New contributor
New contributor
answered Dec 19 at 20:45
Guang Hao Low
912
912
New contributor
New contributor
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
add a comment |
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
add a comment |
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.
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
add a comment |
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.
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
add a comment |
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.
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.
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
add a comment |
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
add a comment |
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.
add a comment |
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.
add a comment |
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.
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.
answered Dec 19 at 21:02
cnada
1,809211
1,809211
add a comment |
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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