Mixing
Has there been any truly ground breaking advance in quantum algorithms since Grover and Shor?
Clash Royale CLAN TAG#URR8PPP
up vote
4
down vote
favorite
(Sorry for a somewhat amateurish question)
I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially solving all sorts of problems by outperforming classical computers, but in practice there were really only two theoretical breakthroughs:
- Shor's algorithm, which did show significant speed up, but which had limited applicability, and wasn't really useful outside of integer factorization.
- Grover's algorithm, which was applicable to a wider category of problems (since it could be used to solve NP-Complete problems), but which only showed polynomial speed-up compared to classical computers.
Quantum annealing was also discussed, but it wasn't clear whether it was really better than classical simulated annealing or not. Measurement based QC and the graph state representation of QC were also hot topics, but nothing definitive had been proved on that front either.
Has any progress in the field of quantum algorithms been made since then? In particular:
- Have there been any truly ground breaking algorithms besides Grover's and Shor's?
- Has there been any progress in defining BQP's relationship to P, BPP and NP?
- Have we made any progress in understanding the nature of quantum speed up other than saying that "it must be because of entanglement"?
quantum-speedup grovers-algorithm shors-algorithm
edited 43 mins ago
DaftWullie
8,0921230
asked 3 hours ago
Alex Kinman
1211
New contributor
Alex Kinman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
4
down vote
favorite
(Sorry for a somewhat amateurish question)
I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially solving all sorts of problems by outperforming classical computers, but in practice there were really only two theoretical breakthroughs:
- Shor's algorithm, which did show significant speed up, but which had limited applicability, and wasn't really useful outside of integer factorization.
- Grover's algorithm, which was applicable to a wider category of problems (since it could be used to solve NP-Complete problems), but which only showed polynomial speed-up compared to classical computers.
Quantum annealing was also discussed, but it wasn't clear whether it was really better than classical simulated annealing or not. Measurement based QC and the graph state representation of QC were also hot topics, but nothing definitive had been proved on that front either.
Has any progress in the field of quantum algorithms been made since then? In particular:
- Have there been any truly ground breaking algorithms besides Grover's and Shor's?
- Has there been any progress in defining BQP's relationship to P, BPP and NP?
- Have we made any progress in understanding the nature of quantum speed up other than saying that "it must be because of entanglement"?
quantum-speedup grovers-algorithm shors-algorithm
edited 43 mins ago
DaftWullie
8,0921230
asked 3 hours ago
Alex Kinman
1211
New contributor
Alex Kinman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
up vote
4
down vote
favorite
up vote
4
down vote
favorite
(Sorry for a somewhat amateurish question)
I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially solving all sorts of problems by outperforming classical computers, but in practice there were really only two theoretical breakthroughs:
- Shor's algorithm, which did show significant speed up, but which had limited applicability, and wasn't really useful outside of integer factorization.
- Grover's algorithm, which was applicable to a wider category of problems (since it could be used to solve NP-Complete problems), but which only showed polynomial speed-up compared to classical computers.
Quantum annealing was also discussed, but it wasn't clear whether it was really better than classical simulated annealing or not. Measurement based QC and the graph state representation of QC were also hot topics, but nothing definitive had been proved on that front either.
Has any progress in the field of quantum algorithms been made since then? In particular:
- Have there been any truly ground breaking algorithms besides Grover's and Shor's?
- Has there been any progress in defining BQP's relationship to P, BPP and NP?
- Have we made any progress in understanding the nature of quantum speed up other than saying that "it must be because of entanglement"?
quantum-speedup grovers-algorithm shors-algorithm
edited 43 mins ago
DaftWullie
8,0921230
asked 3 hours ago
Alex Kinman
1211
New contributor
Alex Kinman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
(Sorry for a somewhat amateurish question)
I studied quantum computing from 2004 to 2007, but I've lost track of the field since then. At the time there was a lot of hype and talk of QC potentially solving all sorts of problems by outperforming classical computers, but in practice there were really only two theoretical breakthroughs:
- Shor's algorithm, which did show significant speed up, but which had limited applicability, and wasn't really useful outside of integer factorization.
- Grover's algorithm, which was applicable to a wider category of problems (since it could be used to solve NP-Complete problems), but which only showed polynomial speed-up compared to classical computers.
Quantum annealing was also discussed, but it wasn't clear whether it was really better than classical simulated annealing or not. Measurement based QC and the graph state representation of QC were also hot topics, but nothing definitive had been proved on that front either.
Has any progress in the field of quantum algorithms been made since then? In particular:
- Have there been any truly ground breaking algorithms besides Grover's and Shor's?
- Has there been any progress in defining BQP's relationship to P, BPP and NP?
- Have we made any progress in understanding the nature of quantum speed up other than saying that "it must be because of entanglement"?
quantum-speedup grovers-algorithm shors-algorithm
quantum-speedup grovers-algorithm shors-algorithm
edited 43 mins ago
DaftWullie
8,0921230
asked 3 hours ago
Alex Kinman
1211
New contributor
Alex Kinman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 43 mins ago
DaftWullie
8,0921230
asked 3 hours ago
Alex Kinman
1211
New contributor
Alex Kinman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 43 mins ago
DaftWullie
8,0921230
edited 43 mins ago
DaftWullie
8,0921230
edited 43 mins ago
DaftWullie
8,0921230
8,0921230
asked 3 hours ago
Alex Kinman
1211
New contributor
Alex Kinman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 3 hours ago
Alex Kinman
1211
asked 3 hours ago
Alex Kinman
1211
1211
New contributor
Alex Kinman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Alex Kinman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Alex Kinman is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Have there been any truly ground breaking algorithms besides Grover's
and Shor's?
It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) and they had killer applications for specific communities.
There have been a few quantum algorithms that have been designed since, and I think three are particularly worthy of mention:
The BQP-complete algorithm for evaluating the Jones polynomial at particular points. I mention this because, aside from more obvious things like Hamiltonian simulation, I believe it was the first BQP-complete algorithm, so it really shows the full power of a quantum computer.
The HHL algorithm for solving linear equations. This is a slightly funny one because it's more like a quantum subroutine, with quantum inputs and outputs. However, it is also BQP-complete and it's receiving a lot of attention at the moment, because of potential applications in machine learning and the like. I guess this is the best candidate for truly ground breaking, but that's a matter of opinion.
Quantum Chemistry. I know very little about these, but the algorithms have developed substantially since the time you mention, and it has always been cited as one of the useful applications of a quantum computer.
Has there been any progress in defining BQP's relationship to P, BPP
and NP?
Essentially, no. We know BQP contains BPP, and we don't know the relation between BQP and NP.
Have we made any progress in understanding the nature of quantum speed
up other than saying that "it must be because of entanglement"?
Even back when you were studying it originally, I would say it was more precisely defined than that. There are (and were) good comparisons between universal gate sets (potentially capable of giving exponential speed-up) and classically simulable gate sets. For example, recall that the Clifford gates produce entanglement but are classically simulable. Not that it's straightforward to state precisely what is required in a more pedagogical manner.
Perhaps where some progress has been made is in terms of other models of computation. For example, the model DQC1 is better understood - this is a model that appears to have some speed-up over classical algorithms but is unlikely to be capable of BQP-complete calculations (but before you get drawn into the hype that you might find online, there is entanglement present during the computation).
On the other hand, the "it's because of entanglement" sort of statement still isn't entirely resolved. Yes, for pure state quantum computation, there must be some entanglement because otherwise the system is easy to simulate, but for mixed separable states, we don't know if they can be used for computations, or if they can be efficiently simulated.
Also, one might try to ask a more insightful question: Have we made any progress in understanding which problems will be amenable to a quantum speed-up? This is subtly different because if you think that a quantum computer gives you new logic gates that a classical computer doesn't have, then it's obvious that to get a speed-up, you must use those new gates. However, it is not clear that every problem is amenable to such benefits. Which ones are? There are classes of problem where one might hope for speed-up, but I think that still relies on individual intuition. That can probably still be said about classical algorithms. You've written an algorithm x. Is there a better classical version? Maybe not, or maybe you're just not spotting it. That's why we don't know if P=NP.
answered 51 mins ago
DaftWullie
8,0921230
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Have there been any truly ground breaking algorithms besides Grover's
and Shor's?
It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) and they had killer applications for specific communities.
There have been a few quantum algorithms that have been designed since, and I think three are particularly worthy of mention:
The BQP-complete algorithm for evaluating the Jones polynomial at particular points. I mention this because, aside from more obvious things like Hamiltonian simulation, I believe it was the first BQP-complete algorithm, so it really shows the full power of a quantum computer.
The HHL algorithm for solving linear equations. This is a slightly funny one because it's more like a quantum subroutine, with quantum inputs and outputs. However, it is also BQP-complete and it's receiving a lot of attention at the moment, because of potential applications in machine learning and the like. I guess this is the best candidate for truly ground breaking, but that's a matter of opinion.
Quantum Chemistry. I know very little about these, but the algorithms have developed substantially since the time you mention, and it has always been cited as one of the useful applications of a quantum computer.
Has there been any progress in defining BQP's relationship to P, BPP
and NP?
Essentially, no. We know BQP contains BPP, and we don't know the relation between BQP and NP.
Have we made any progress in understanding the nature of quantum speed
up other than saying that "it must be because of entanglement"?
Even back when you were studying it originally, I would say it was more precisely defined than that. There are (and were) good comparisons between universal gate sets (potentially capable of giving exponential speed-up) and classically simulable gate sets. For example, recall that the Clifford gates produce entanglement but are classically simulable. Not that it's straightforward to state precisely what is required in a more pedagogical manner.
Perhaps where some progress has been made is in terms of other models of computation. For example, the model DQC1 is better understood - this is a model that appears to have some speed-up over classical algorithms but is unlikely to be capable of BQP-complete calculations (but before you get drawn into the hype that you might find online, there is entanglement present during the computation).
On the other hand, the "it's because of entanglement" sort of statement still isn't entirely resolved. Yes, for pure state quantum computation, there must be some entanglement because otherwise the system is easy to simulate, but for mixed separable states, we don't know if they can be used for computations, or if they can be efficiently simulated.
Also, one might try to ask a more insightful question: Have we made any progress in understanding which problems will be amenable to a quantum speed-up? This is subtly different because if you think that a quantum computer gives you new logic gates that a classical computer doesn't have, then it's obvious that to get a speed-up, you must use those new gates. However, it is not clear that every problem is amenable to such benefits. Which ones are? There are classes of problem where one might hope for speed-up, but I think that still relies on individual intuition. That can probably still be said about classical algorithms. You've written an algorithm x. Is there a better classical version? Maybe not, or maybe you're just not spotting it. That's why we don't know if P=NP.
answered 51 mins ago
DaftWullie
8,0921230
add a comment |Â
up vote
2
down vote
Have there been any truly ground breaking algorithms besides Grover's
and Shor's?
It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) and they had killer applications for specific communities.
There have been a few quantum algorithms that have been designed since, and I think three are particularly worthy of mention:
The BQP-complete algorithm for evaluating the Jones polynomial at particular points. I mention this because, aside from more obvious things like Hamiltonian simulation, I believe it was the first BQP-complete algorithm, so it really shows the full power of a quantum computer.
The HHL algorithm for solving linear equations. This is a slightly funny one because it's more like a quantum subroutine, with quantum inputs and outputs. However, it is also BQP-complete and it's receiving a lot of attention at the moment, because of potential applications in machine learning and the like. I guess this is the best candidate for truly ground breaking, but that's a matter of opinion.
Quantum Chemistry. I know very little about these, but the algorithms have developed substantially since the time you mention, and it has always been cited as one of the useful applications of a quantum computer.
Has there been any progress in defining BQP's relationship to P, BPP
and NP?
Essentially, no. We know BQP contains BPP, and we don't know the relation between BQP and NP.
Have we made any progress in understanding the nature of quantum speed
up other than saying that "it must be because of entanglement"?
Even back when you were studying it originally, I would say it was more precisely defined than that. There are (and were) good comparisons between universal gate sets (potentially capable of giving exponential speed-up) and classically simulable gate sets. For example, recall that the Clifford gates produce entanglement but are classically simulable. Not that it's straightforward to state precisely what is required in a more pedagogical manner.
Perhaps where some progress has been made is in terms of other models of computation. For example, the model DQC1 is better understood - this is a model that appears to have some speed-up over classical algorithms but is unlikely to be capable of BQP-complete calculations (but before you get drawn into the hype that you might find online, there is entanglement present during the computation).
On the other hand, the "it's because of entanglement" sort of statement still isn't entirely resolved. Yes, for pure state quantum computation, there must be some entanglement because otherwise the system is easy to simulate, but for mixed separable states, we don't know if they can be used for computations, or if they can be efficiently simulated.
Also, one might try to ask a more insightful question: Have we made any progress in understanding which problems will be amenable to a quantum speed-up? This is subtly different because if you think that a quantum computer gives you new logic gates that a classical computer doesn't have, then it's obvious that to get a speed-up, you must use those new gates. However, it is not clear that every problem is amenable to such benefits. Which ones are? There are classes of problem where one might hope for speed-up, but I think that still relies on individual intuition. That can probably still be said about classical algorithms. You've written an algorithm x. Is there a better classical version? Maybe not, or maybe you're just not spotting it. That's why we don't know if P=NP.
answered 51 mins ago
DaftWullie
8,0921230
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Have there been any truly ground breaking algorithms besides Grover's
and Shor's?
It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) and they had killer applications for specific communities.
There have been a few quantum algorithms that have been designed since, and I think three are particularly worthy of mention:
The BQP-complete algorithm for evaluating the Jones polynomial at particular points. I mention this because, aside from more obvious things like Hamiltonian simulation, I believe it was the first BQP-complete algorithm, so it really shows the full power of a quantum computer.
The HHL algorithm for solving linear equations. This is a slightly funny one because it's more like a quantum subroutine, with quantum inputs and outputs. However, it is also BQP-complete and it's receiving a lot of attention at the moment, because of potential applications in machine learning and the like. I guess this is the best candidate for truly ground breaking, but that's a matter of opinion.
Quantum Chemistry. I know very little about these, but the algorithms have developed substantially since the time you mention, and it has always been cited as one of the useful applications of a quantum computer.
Has there been any progress in defining BQP's relationship to P, BPP
and NP?
Essentially, no. We know BQP contains BPP, and we don't know the relation between BQP and NP.
Have we made any progress in understanding the nature of quantum speed
up other than saying that "it must be because of entanglement"?
Even back when you were studying it originally, I would say it was more precisely defined than that. There are (and were) good comparisons between universal gate sets (potentially capable of giving exponential speed-up) and classically simulable gate sets. For example, recall that the Clifford gates produce entanglement but are classically simulable. Not that it's straightforward to state precisely what is required in a more pedagogical manner.
Perhaps where some progress has been made is in terms of other models of computation. For example, the model DQC1 is better understood - this is a model that appears to have some speed-up over classical algorithms but is unlikely to be capable of BQP-complete calculations (but before you get drawn into the hype that you might find online, there is entanglement present during the computation).
On the other hand, the "it's because of entanglement" sort of statement still isn't entirely resolved. Yes, for pure state quantum computation, there must be some entanglement because otherwise the system is easy to simulate, but for mixed separable states, we don't know if they can be used for computations, or if they can be efficiently simulated.
Also, one might try to ask a more insightful question: Have we made any progress in understanding which problems will be amenable to a quantum speed-up? This is subtly different because if you think that a quantum computer gives you new logic gates that a classical computer doesn't have, then it's obvious that to get a speed-up, you must use those new gates. However, it is not clear that every problem is amenable to such benefits. Which ones are? There are classes of problem where one might hope for speed-up, but I think that still relies on individual intuition. That can probably still be said about classical algorithms. You've written an algorithm x. Is there a better classical version? Maybe not, or maybe you're just not spotting it. That's why we don't know if P=NP.
answered 51 mins ago
DaftWullie
8,0921230
Have there been any truly ground breaking algorithms besides Grover's
and Shor's?
It depends on what you mean by "truly ground breaking". Grover's and Shor's are particularly unique because they were really the first instances that showed particularly valuable types of speed-up with a quantum computer (e.g. the presumed exponential improvement for Shor) and they had killer applications for specific communities.
There have been a few quantum algorithms that have been designed since, and I think three are particularly worthy of mention:
The BQP-complete algorithm for evaluating the Jones polynomial at particular points. I mention this because, aside from more obvious things like Hamiltonian simulation, I believe it was the first BQP-complete algorithm, so it really shows the full power of a quantum computer.
The HHL algorithm for solving linear equations. This is a slightly funny one because it's more like a quantum subroutine, with quantum inputs and outputs. However, it is also BQP-complete and it's receiving a lot of attention at the moment, because of potential applications in machine learning and the like. I guess this is the best candidate for truly ground breaking, but that's a matter of opinion.
Quantum Chemistry. I know very little about these, but the algorithms have developed substantially since the time you mention, and it has always been cited as one of the useful applications of a quantum computer.
Has there been any progress in defining BQP's relationship to P, BPP
and NP?
Essentially, no. We know BQP contains BPP, and we don't know the relation between BQP and NP.
Have we made any progress in understanding the nature of quantum speed
up other than saying that "it must be because of entanglement"?
Even back when you were studying it originally, I would say it was more precisely defined than that. There are (and were) good comparisons between universal gate sets (potentially capable of giving exponential speed-up) and classically simulable gate sets. For example, recall that the Clifford gates produce entanglement but are classically simulable. Not that it's straightforward to state precisely what is required in a more pedagogical manner.
Perhaps where some progress has been made is in terms of other models of computation. For example, the model DQC1 is better understood - this is a model that appears to have some speed-up over classical algorithms but is unlikely to be capable of BQP-complete calculations (but before you get drawn into the hype that you might find online, there is entanglement present during the computation).
On the other hand, the "it's because of entanglement" sort of statement still isn't entirely resolved. Yes, for pure state quantum computation, there must be some entanglement because otherwise the system is easy to simulate, but for mixed separable states, we don't know if they can be used for computations, or if they can be efficiently simulated.
Also, one might try to ask a more insightful question: Have we made any progress in understanding which problems will be amenable to a quantum speed-up? This is subtly different because if you think that a quantum computer gives you new logic gates that a classical computer doesn't have, then it's obvious that to get a speed-up, you must use those new gates. However, it is not clear that every problem is amenable to such benefits. Which ones are? There are classes of problem where one might hope for speed-up, but I think that still relies on individual intuition. That can probably still be said about classical algorithms. You've written an algorithm x. Is there a better classical version? Maybe not, or maybe you're just not spotting it. That's why we don't know if P=NP.
answered 51 mins ago
DaftWullie
8,0921230
answered 51 mins ago
DaftWullie
8,0921230
answered 51 mins ago
DaftWullie
8,0921230
answered 51 mins ago
DaftWullie
8,0921230
8,0921230
add a comment |Â
add a comment |Â
Alex Kinman is a new contributor. Be nice, and check out our Code of Conduct.
Alex Kinman is a new contributor. Be nice, and check out our Code of Conduct.
Alex Kinman is a new contributor. Be nice, and check out our Code of Conduct.
Alex Kinman is a new contributor. Be nice, and check out our Code of Conduct.
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fquantumcomputing.stackexchange.com%2fquestions%2f4263%2fhas-there-been-any-truly-ground-breaking-advance-in-quantum-algorithms-since-gro%23new-answer', 'question_page');
);
Post as a guest
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
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
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
