Disentangling the facts from the hype of quantum computing(spectrum.ieee.org)
spectrum.ieee.org
Disentangling the facts from the hype of quantum computing
https://spectrum.ieee.org/ieee-quantum-week
99 comments
If I invest right now, what are the chances that this round strikes it rich? The problem is that if a breakthrough is not achieved in this particular round then the company essentially goes bankrupt and my investment is worth zero.
Quantum is far enough away that unless you have deep pockets it's a donation to a charitable cause. The capital requirements are large enough that profits will be sucked up by later investors who would sooner let the company go bankrupt than let you get a decent return on your money.
Quantum is far enough away that unless you have deep pockets it's a donation to a charitable cause. The capital requirements are large enough that profits will be sucked up by later investors who would sooner let the company go bankrupt than let you get a decent return on your money.
To be fair, i think literally anything is more worthy of funding than web3.
I’m anti-crypto as a solution to currency but I completely disagree here. Trustless databases and trustless distributed data has so many practical use cases in the corporate and political world that I think you’d have to be trying to not think of one readily.
Getting that architecture down is worth web3, even if none of the platforms and services continue on.
Getting that architecture down is worth web3, even if none of the platforms and services continue on.
There is no such thing as a trustable trustless database for anything except money. For every other piece of information that we care about, trust in the source is inevitable.
Nope not true at all. Every industry has shared information between corporations. The sciences are ripe for trustless data sets between antagonistic entities (see: nation states.)
Trustless doesn’t mean every individual human being is an equal in the chain. The more applicable situation is between organization and higher. If you think all problems are just money problems you haven’t solved many large scale real world problems.
Trustless doesn’t mean every individual human being is an equal in the chain. The more applicable situation is between organization and higher. If you think all problems are just money problems you haven’t solved many large scale real world problems.
There are two kinds of facts: facts about the real world, and digital facts. Digital facts can be secured with fancy cryptography in various ways leading to the ability of a trustless database holding such facts - such as a (secured) git repo or the Bitcoin blockchain.
Facts about the real world are true or false about the real world, you can't cryptographically secure them. I can trustlessly store the fact "I am Donald Trump" in some DB, I can prove cryptographically that I stored that fact, but there is no way to conclude from this that I am in fact Donald Trump.
For any digital fact, the relationship between it and a physical fact can only be established by a trusted entity. A government office can digitally sign a statement that the holder of some private key is indeed Donald Trump, and you can then believe that any statement signed by that private key was signed by Donald Trump - IF you trust the government.
Similarly, whether some scientific data set is held in a Chinese RDBMS controlled by a Chinese university or whether it is stored on some public block chain, I have more or less the same amount of trust for that data set.
Facts about the real world are true or false about the real world, you can't cryptographically secure them. I can trustlessly store the fact "I am Donald Trump" in some DB, I can prove cryptographically that I stored that fact, but there is no way to conclude from this that I am in fact Donald Trump.
For any digital fact, the relationship between it and a physical fact can only be established by a trusted entity. A government office can digitally sign a statement that the holder of some private key is indeed Donald Trump, and you can then believe that any statement signed by that private key was signed by Donald Trump - IF you trust the government.
Similarly, whether some scientific data set is held in a Chinese RDBMS controlled by a Chinese university or whether it is stored on some public block chain, I have more or less the same amount of trust for that data set.
"Trustless" and "distributed" are ambigious words that means a lot of different things. Generally there is a mismatch between the type of distributed trustlessness that web3 talks about and all those "practical use cases in the corporate and political world".
That depends on the company. Yeah Ethereum is a meme with tons of meme companies but I assure you there are web3 companies solving real problems you just haven’t heard of them because the things they’re solving aren’t sexy memes like anti-government currencies.
Yeah well, people have been saying that for years, and the years go by, and yet i still haven't heard of these companies.
Market cap is BS in crypto. Last transaction price * number of coins. Means nothing because volume/liquidity isn’t there.
Speaking as an quantum computing academic, I would suggest that money should be redirected from quantum computing into all kinds of biotech, except quantum computing based biotech. There’s never too little money invested in biotech research (as clinical as you can manage), only too much money off siphoned by lab reagent and equipment manufacturers. Unfortunately, non-biotech VCs have even less understanding of this tech than even quantum. That is, assuming most physicists “don’t even understand quantum” — hey, that is why I am a physicist, not a VC. But might considering becoming one after I sell my billion dollar bootstrapped QC company. Yep! The first QC giant will not take —or need—outside funding, for bloody obvious reasons. Just as the first hegemonic semitech company (Intel) birthed Venture Capital (and just like CAS hegemon Wolfram birthed a new kind of science /s) the first hegemonic qtech company will birth a new funding model (/s?)
I'm not sure where this is coming from. So you really believe the dollars that Facebook spends on the metaverse was just waiting to be pumped into quantum computing?
This comment really sounds like: "why go to Mars, we haven't even explored our own oceans". As if those are somehow mutually exclusive.
This comment really sounds like: "why go to Mars, we haven't even explored our own oceans". As if those are somehow mutually exclusive.
Right now, nuclear fusion reactors seems to be the thing that's ripe for investment. There are a lot of promising advances, maybe a Project Manhattan-style push might be worth trying.
What I’m not clear on is whether quantum computing can be best advanced through $billions of VC money competing for hypothetical future profit, or whether it is still a scientific research project which would benefit from a smaller, more focused and less hype-driven approach.
A lot of what we see reported as progress is academic or quasi-academic papers. Google has the cash to not care too much if its research never turns a profit. Those who are investing may see it as a long-term moonshot or hedge, without any great expectations of imminent profit. The bottleneck may be the number of scientists with good ideas, rather than the amount of cash available.
A lot of what we see reported as progress is academic or quasi-academic papers. Google has the cash to not care too much if its research never turns a profit. Those who are investing may see it as a long-term moonshot or hedge, without any great expectations of imminent profit. The bottleneck may be the number of scientists with good ideas, rather than the amount of cash available.
I predict that quantum computing is possible but you still have to take into account the addressable market which appears to be very small. Even assuming they work perfectly, quantum computers just aren't good for much.
Yes, we will never need more than 12 quantum computers or so /s
Computers today are used to solve the problems computers can solve: this is as vastly larger class of problems than envisioned by anyone 50 or 70 years ago, but there are still many computational problems that we do not solve.
These unsolved problems are often only known by domain experts with a deep understanding of why a specific domain is addressed by a given model.
Computers today are used to solve the problems computers can solve: this is as vastly larger class of problems than envisioned by anyone 50 or 70 years ago, but there are still many computational problems that we do not solve.
These unsolved problems are often only known by domain experts with a deep understanding of why a specific domain is addressed by a given model.
What’s the argument for it not being possible?
Superposition is real, the speed up will be real once it scales up.
I know there’s a lot of details to figure out but I’m not aware of any that seem insurmountable given all the effort going into it and incremental progress that continues to be made.
Superposition is real, the speed up will be real once it scales up.
I know there’s a lot of details to figure out but I’m not aware of any that seem insurmountable given all the effort going into it and incremental progress that continues to be made.
I think the current argument against them is that some people think that the error rate of qubits will grow exponentially with size of machine in such a way that the error rate will outrun the ability of error correcting codes to fix errors. (Not a quantum scientist. I probably misunderstand and i have no idea how likely it is)
> Superposition is real, the speed up will be real once it scales up.
To be clear, they only speed up very select problems. It is not a general speed up.
> Superposition is real, the speed up will be real once it scales up.
To be clear, they only speed up very select problems. It is not a general speed up.
I just find it hard to believe that physical reality will let us do reliable computations with superpositions of 2^1024 states. I suspect that the theory of quantum physics is some excellent approximation of physical reality that will breakdown at such absurd levels of precision.
My argument would be superposition, is a kind of mathematical abstraction, that is not directly useful in the real world. Quantum computers are a kind of analog computer, and suffer from analog computer problems.
??
You dont believe that the experiments observing superposition are real?
(Im only attacking the, its a mathematical abstraction, bit. Whether or not superposition can be pragmatically harnessed to make qc is a separate question)
You dont believe that the experiments observing superposition are real?
(Im only attacking the, its a mathematical abstraction, bit. Whether or not superposition can be pragmatically harnessed to make qc is a separate question)
clearly some kind of superposition is real, in the same sense that classical waves can superimpose. However there is a wild gulf between that and what is commonly accepted with multi-particle quantum mechanics, which is that the universe is N-dimensional, where N is the number of particles, and that arbitrary configurations in some slice of those N dimensions can be independent of some other slice. This hasn't really been tested, and in fact quantum computing is the first real test of it. And it's not looking good for that theory.
So to be clear - your view is that quantum computers can't exist because quantum mechanics is false?
Well, I would say QM is an approximation of some better and more accurate theory. In my view, multi-particle quantum mechanics is pretty clearly a kind of gross hack - using a very large dimensional space so you can write down a linear theory - instead of using a smaller dimensional space with non-linear interactions. Quantum computing assumes the very large dimensional space is actually real. So we'll see if that is the case.
How would you explain the fact that the experiments with current quantum computers support the theory?
Well, the status of the experiments is unclear - since the Google paper was published, the state of the art in classical spoofing of the same result has improved by about 10,000 times, and the results obtained by Google in 300s have been obtained by a classical computer in 1s or so. Note that the classical computer was much much larger, so there is still a huge difference in number of operations executed that still gives a notion of quantum supremacy. It is harder though to be sure now that the result will stand compared to when it was first announced.
It should also be noted that there is no prood right that any of the known quantum algorithms give an exponential speedup over the best possible classical algorithms. In particular, integer factoring (that Shor's algorithm solves) is believed by many to have a yet undiscovered polynomial-time classical algorithm.
Separately, it should be remembered that quantum mechanics has large difficulties when applied on classical scales in reproducing classical observations. This is an inherent problem, since QM is an almost linear theory, while there are many extremely well confirmed non-linear processes in classical and relativistic physics. The only possible source of that nonlinearity from QM is also the least well understood aspect of the theory - Born rule (measurement postulate, wave function collapse).
For example, if you try to use QM to describe the motion of a double-pendulum, you will get a completely wrong result, even if applying the Born rule at the end to get a single definite result with some probability. You instead have to add multiple intermediate applications of the Born rule to get the non-linear behavior that is observed in practice.
It should also be noted that there is no prood right that any of the known quantum algorithms give an exponential speedup over the best possible classical algorithms. In particular, integer factoring (that Shor's algorithm solves) is believed by many to have a yet undiscovered polynomial-time classical algorithm.
Separately, it should be remembered that quantum mechanics has large difficulties when applied on classical scales in reproducing classical observations. This is an inherent problem, since QM is an almost linear theory, while there are many extremely well confirmed non-linear processes in classical and relativistic physics. The only possible source of that nonlinearity from QM is also the least well understood aspect of the theory - Born rule (measurement postulate, wave function collapse).
For example, if you try to use QM to describe the motion of a double-pendulum, you will get a completely wrong result, even if applying the Born rule at the end to get a single definite result with some probability. You instead have to add multiple intermediate applications of the Born rule to get the non-linear behavior that is observed in practice.
> It should also be noted that there is no prood right that any of the known quantum algorithms give an exponential speedup over the best possible classical algorithms.
True, but we also can't even prove P!=NP, which seems (intuitively) like it should be much easier than proving that there exists an exponential speedup with quantum algorithms. I feel like this statement mostly just says we have a far way to go in understanding the relations between complexity classes. Its not like we have proven all the "obvious" separations between complexity classes and qunatum stuff is just a stubborn hold out.
True, but we also can't even prove P!=NP, which seems (intuitively) like it should be much easier than proving that there exists an exponential speedup with quantum algorithms. I feel like this statement mostly just says we have a far way to go in understanding the relations between complexity classes. Its not like we have proven all the "obvious" separations between complexity classes and qunatum stuff is just a stubborn hold out.
Oh, absolutely, I didn't mean to imply that this should be easy. It's just important to note in these discussions what we do know for sure and what is still debatable.
My point was that one way of accounting for a belief that QCs are not fundamentally exponentially faster than classical computers despite the experiments we've seen from Google is to believe that we will find classical equivalents of every quantum algorithm that shows such a speedup. While few believe this in the community, and for good reasons, it is not proven to be a silly belief yet.
By the way, I will also mention that if P=NP (not that anyone thinks this is remotely likely), that would also imply that quantum computers have no exponential advantage over classical ones.
My point was that one way of accounting for a belief that QCs are not fundamentally exponentially faster than classical computers despite the experiments we've seen from Google is to believe that we will find classical equivalents of every quantum algorithm that shows such a speedup. While few believe this in the community, and for good reasons, it is not proven to be a silly belief yet.
By the way, I will also mention that if P=NP (not that anyone thinks this is remotely likely), that would also imply that quantum computers have no exponential advantage over classical ones.
Joscha Bach has some interesting arguments against it: http://bach.ai/quantum-computers-wont-work/
> Superposition is real
Really? I wasn't aware science told us what was real.
It's called the "Copenhagen interpretation" for a reason.
Really? I wasn't aware science told us what was real.
It's called the "Copenhagen interpretation" for a reason.
Do other QM interpretations predict that quantum computers wouldn't be able to benefit from superposing N qubits over 2^N (possible) output states? As far as I understand, it's not just Copenhagen that allows for this.
Would an interpretation need to reject Bell's theorem to get there? Or could it not include superposition but still keep all of Bell's theorem?
Would an interpretation need to reject Bell's theorem to get there? Or could it not include superposition but still keep all of Bell's theorem?
Rovelli’s work on relational QM suggests to me that superposition-as-real in the Copenhagen interpretation is false, a misunderstanding of how to incorporate the observer into the equation.
Once the observer (or the affected system, same thing, in the end) is incorporated, a lot of the things about superposition that needed interpretation disappear.
Read Helgoland for more.
(My physics degree was a long time ago and my math is quite out of date. While Rovelli doesn’t discuss QC in the book, his take on what superposition is not has strong implications for QC AFAICT.)
Once the observer (or the affected system, same thing, in the end) is incorporated, a lot of the things about superposition that needed interpretation disappear.
Read Helgoland for more.
(My physics degree was a long time ago and my math is quite out of date. While Rovelli doesn’t discuss QC in the book, his take on what superposition is not has strong implications for QC AFAICT.)
Thanks for the suggestion. I have his other book "Order of time" (beside me no less) that I have yet to finish but have liked so far.
That’s a good one, next in my reread list.
More space travel?
This disentangling continues to entangle the most salient aspect of this -- the definition of a qubit itself.
Claiming a device with hundreds of qubits exists is a stretch because we have modified the target. Current generation of QC's are targeting NISQ (Noisy Intermediate-Scale Quantum) architectures. They are not general-purpose computers; they are instead attempting to address the central problem of quantum computing and "quantum supremacy" -- namely, whether there exist computational problems for which classical computers demonstrate exponential growth in time complexity, but quantum computers show sub-exponential growth.
It remains unclear whether even this is possible, much less whether it is possible to build error-correction systems that will allow for the creation of a general-purpose programmable quantum computer. The oft-cited examples of quantum computers factoring small numbers with Shor's algorithm demonstrate that the principles are correct, but do not actually factor the numbers; instead they basically assign probabilities; effectively (not literally) saying that there is a non-zero probability that 11 is a factor of 21. At this point it does not appear that any of the solutions (photonics, NMR) for these toy problems can scale at all -- I would love to see more pre-registration for attempts to factor larger numbers to get a better idea of why they are failing, we have precious few examples of the breakdown.
When we compare where we are compared to digital computers, we are still in the pre-vacuum-tube era; maybe even the pre-differential era if we look at mechanical computers.
Predicting timelines for this is a fools errand at this point -- it could be tomorrow with a crazy breakthrough; it could be 100 years; it could (and this is my view) not even be possible.
Claiming a device with hundreds of qubits exists is a stretch because we have modified the target. Current generation of QC's are targeting NISQ (Noisy Intermediate-Scale Quantum) architectures. They are not general-purpose computers; they are instead attempting to address the central problem of quantum computing and "quantum supremacy" -- namely, whether there exist computational problems for which classical computers demonstrate exponential growth in time complexity, but quantum computers show sub-exponential growth.
It remains unclear whether even this is possible, much less whether it is possible to build error-correction systems that will allow for the creation of a general-purpose programmable quantum computer. The oft-cited examples of quantum computers factoring small numbers with Shor's algorithm demonstrate that the principles are correct, but do not actually factor the numbers; instead they basically assign probabilities; effectively (not literally) saying that there is a non-zero probability that 11 is a factor of 21. At this point it does not appear that any of the solutions (photonics, NMR) for these toy problems can scale at all -- I would love to see more pre-registration for attempts to factor larger numbers to get a better idea of why they are failing, we have precious few examples of the breakdown.
When we compare where we are compared to digital computers, we are still in the pre-vacuum-tube era; maybe even the pre-differential era if we look at mechanical computers.
Predicting timelines for this is a fools errand at this point -- it could be tomorrow with a crazy breakthrough; it could be 100 years; it could (and this is my view) not even be possible.
> The oft-cited examples of quantum computers factoring small numbers with Shor's algorithm demonstrate that the principles are correct, but do not actually factor the numbers; instead they basically assign probabilities; effectively (not literally) saying that there is a non-zero probability that 11 is a factor of 21.
I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic. It's a feature of the calculation, not a bug.
At any rate, it's not really a problem if the factorization is sometimes incorrect. If you doubt the result, just multiply the numbers together on a classical computer. If the numbers don't match, repeat the process. Even if your quantum computer only yields the correct result 50% of the time, you'd still be better off using a quantum computer than brute forcing for large enough numbers.
(Of course, and I suppose this is your point, quantum computers with a sufficient numbers of qubits to prove supremacy in factorization do not yet exist.)
I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic. It's a feature of the calculation, not a bug.
At any rate, it's not really a problem if the factorization is sometimes incorrect. If you doubt the result, just multiply the numbers together on a classical computer. If the numbers don't match, repeat the process. Even if your quantum computer only yields the correct result 50% of the time, you'd still be better off using a quantum computer than brute forcing for large enough numbers.
(Of course, and I suppose this is your point, quantum computers with a sufficient numbers of qubits to prove supremacy in factorization do not yet exist.)
> (Of course, and I suppose this is your point, quantum computers with a sufficient numbers of qubits to prove supremacy in factorization do not yet exist.)
That is sort of the point, but not quite. We do not have general-purpose quantum computers with even a single qubit! We've redefined qubits in the NISQ context for the purpose of demonstrating quantum supremacy, and that is all they are good for. If Google expands Sycamore to hold a billion qubits, it will not be capable of factoring 6.
The hope is that if we accomplished that, then we could use those learnings to make single-purpose quantum computers or general-purpose quantum computers. But we haven't gotten there yet. This is not a matter of adding more NISQ qubits to any of the existing projects!
> result 50% of the time
50% would be astonishingly good. If all the quantum computer can say is "well, one of these sqrt(N) possibilities are 50% likely to be a factor" then we haven't improved anything. And the IBM result on attempting to factor 35 seems to fall into this pattern; the noise level is too high.
That is sort of the point, but not quite. We do not have general-purpose quantum computers with even a single qubit! We've redefined qubits in the NISQ context for the purpose of demonstrating quantum supremacy, and that is all they are good for. If Google expands Sycamore to hold a billion qubits, it will not be capable of factoring 6.
The hope is that if we accomplished that, then we could use those learnings to make single-purpose quantum computers or general-purpose quantum computers. But we haven't gotten there yet. This is not a matter of adding more NISQ qubits to any of the existing projects!
> result 50% of the time
50% would be astonishingly good. If all the quantum computer can say is "well, one of these sqrt(N) possibilities are 50% likely to be a factor" then we haven't improved anything. And the IBM result on attempting to factor 35 seems to fall into this pattern; the noise level is too high.
> I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic.
The substrate of physical digital computers is analog and probabilistic too. We just put a threshold above which a logic signal is considered 1 and we give enough time for a state transition to be considered done. We also throw in the mix a large number of electrons so that it's very likely that the aggregate effect produces a definite answer.
This is not all that unlike what we have to do with quantum computers. You just have to find a suitable threshold after which your desired answer is sufficiently likely to come out.
The substrate of physical digital computers is analog and probabilistic too. We just put a threshold above which a logic signal is considered 1 and we give enough time for a state transition to be considered done. We also throw in the mix a large number of electrons so that it's very likely that the aggregate effect produces a definite answer.
This is not all that unlike what we have to do with quantum computers. You just have to find a suitable threshold after which your desired answer is sufficiently likely to come out.
But even under these conditions no team has been able to demonstrate a working implementation of Shor's algorithm that can factor arbitrary 6-bit prime products. Quoting from [1]:
> In 2019 an attempt was made to factor the number {\displaystyle 35}{\displaystyle 35} using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.[13] Though larger numbers have been factored by quantum computers using other algorithms,[14] these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms.
[1] https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also
> In 2019 an attempt was made to factor the number {\displaystyle 35}{\displaystyle 35} using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.[13] Though larger numbers have been factored by quantum computers using other algorithms,[14] these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms.
[1] https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also
> whether there exist computational problems for which classical computers demonstrate exponential growth in time complexity, but quantum computers show sub-exponential growth.
> It remains unclear whether even this is possible
"Quantum supremacy" by this definition has already been experimentally demonstrated, and it's not a high bar to meet. Like saying that if I let go of a feather in a windy area and measure how long it takes to fall to the ground with a stopwatch, that is "feather drop timing supremacy" because I have solved the problem of determining how long the feather takes to fall easily, while a classical computer would need to do complex physics simulations to get the same result.
What is hard and interesting is to find a useful computational problem for which quantum computers are much better than classical ones.
"Quantum supremacy" by this definition has already been experimentally demonstrated, and it's not a high bar to meet. Like saying that if I let go of a feather in a windy area and measure how long it takes to fall to the ground with a stopwatch, that is "feather drop timing supremacy" because I have solved the problem of determining how long the feather takes to fall easily, while a classical computer would need to do complex physics simulations to get the same result.
What is hard and interesting is to find a useful computational problem for which quantum computers are much better than classical ones.
I agree that this is the problem that we are effectively trying to solve. The problem with the feather analogy is that there's an initial condition problem that is basically unresolvable. Replicating them in such a way that the result of physically dropping the feather is identical between runs of this computer is far beyond intractable, much less representing them in such a way that you can compare the output of a classical computer in this regard.
The NMR results from factoring 15 [1] are incredibly fascinating. Here the quantum computer is just a molecule, and using NMR we can get a precise view of the initial conditions and the time evolution. We're just asking the molecule to molecule itself and measuring the outcome. This unfortunately does not appear to scale, so it's impossible to say if we are demonstrating quantum supremacy, but the experimental design blows my mind.
[1] https://cryptome.org/shor-nature.pdf
The NMR results from factoring 15 [1] are incredibly fascinating. Here the quantum computer is just a molecule, and using NMR we can get a precise view of the initial conditions and the time evolution. We're just asking the molecule to molecule itself and measuring the outcome. This unfortunately does not appear to scale, so it's impossible to say if we are demonstrating quantum supremacy, but the experimental design blows my mind.
[1] https://cryptome.org/shor-nature.pdf
I think you are having a relatively common misunderstanding.
Indeed, just having some analog process run itself is a boring example of "supremacy". https://www.smbc-comics.com/comic/2013-07-19
A "useful" computation is indeed the important final proof of supremacy.
But intermediary results of "programmable" but useless computation is a pretty amazing achievement on its own, and it is not just "an analog process running itself". The distinction is described quite well here and it really matters to computational complexity theory https://scottaaronson.blog/?p=5460
Indeed, just having some analog process run itself is a boring example of "supremacy". https://www.smbc-comics.com/comic/2013-07-19
A "useful" computation is indeed the important final proof of supremacy.
But intermediary results of "programmable" but useless computation is a pretty amazing achievement on its own, and it is not just "an analog process running itself". The distinction is described quite well here and it really matters to computational complexity theory https://scottaaronson.blog/?p=5460
AGI incorporating a Scott Aaronson brain emulation will solve quantum computing within 20 years.
> Let’s remember that it took Google 53 qubits to create an application that could accomplish a supercomputer function. If we want to explore new applications that go beyond today’s supercomputers, we’ll need to see system sizes that are orders of magnitude larger.
Although the current order of magnitude (10s of qubits) are sufficient (on paper) for doing certain tasks faster than supercomputers of today, we need to go to 100-1000 qubits order for error-corrected results. Maintaining coherence for long enough to be able to do useful calculations in 10s of qubits has still been a challenge, let alone the designs for 100s of qubits.
Although the current order of magnitude (10s of qubits) are sufficient (on paper) for doing certain tasks faster than supercomputers of today, we need to go to 100-1000 qubits order for error-corrected results. Maintaining coherence for long enough to be able to do useful calculations in 10s of qubits has still been a challenge, let alone the designs for 100s of qubits.
> Let’s remember that it took Google 53 qubits to create an application that could accomplish a supercomputer function. If we want to explore new applications that go beyond today’s supercomputers, we’ll need to see system sizes that are orders of magnitude larger.
And it turns out that Google didn't even do that. Further research [1] has indicated that the suspected case of quantum supremacy was not valid, as the problem can be solved classically without a supercomputer. So we have yet to see a demonstration of quantum supremacy from an NISQ system.
[1] https://gilkalai.wordpress.com/2022/08/06/ordinary-computers...
And it turns out that Google didn't even do that. Further research [1] has indicated that the suspected case of quantum supremacy was not valid, as the problem can be solved classically without a supercomputer. So we have yet to see a demonstration of quantum supremacy from an NISQ system.
[1] https://gilkalai.wordpress.com/2022/08/06/ordinary-computers...
It is indeed incredibly exciting when better classical algorithms are found. But if Google were using 10 more qubits, then that classical algorithm would have failed. That is at the root of supremacy experiments: a minor increase in the number of qubits leads to exponential difficulty in classically faking the result. And that type of push-and-pull will continue for another few years until we have a "useful" example of supremacy. That does not de-value the current technology demonstrators that are paving the way.
> But if Google were using 10 more qubits, then that classical algorithm would have failed
That's a big maybe -- the paper that describes the classical algorithm indicates that they achieved significantly higher fidelity than that reported by the Sycamore paper, so it's unclear if the quantum computer was even giving valid results at more than 12-14 qubits.
That's a big maybe -- the paper that describes the classical algorithm indicates that they achieved significantly higher fidelity than that reported by the Sycamore paper, so it's unclear if the quantum computer was even giving valid results at more than 12-14 qubits.
What are the odds quantum algorithms end up as a no true Scotsman (but without the fallacy) where everyone found turns out to have some classical workaround/solution?
If that happens, that would be absolutely monumental discovery, not just for CS, but for fundamental physics. I am a researcher working on building quantum computer hardware. If the whole premise of my career vanishes one day because Computational Complexity theorists find a way to prove that BQP as a complexity class is not more powerful than BPP, I would be *happier* than if I successfully build a quantum computer (although I probably would need to find a different job at that point). Such a discovery would shatter our understanding of the physical world and of abstract mathematics.
Yep this is what I expected but am not a physicist nor work on quantum computers. Thanks.
I think the odds are 0 in general, but perhaps higher for many actually "useful" algorithms.
Take grover's algorithm (basically find an item in a list or bruteforce something in O(sqrt(n)) time). The current best classical algorithm to bruteforce something is try every possibility, taking about n/2 guesses on average. The quantum version takes O(sqrt(n)). We are never going to be able to bruteforce with a normal computer faster than guessing all possibilities.
Take grover's algorithm (basically find an item in a list or bruteforce something in O(sqrt(n)) time). The current best classical algorithm to bruteforce something is try every possibility, taking about n/2 guesses on average. The quantum version takes O(sqrt(n)). We are never going to be able to bruteforce with a normal computer faster than guessing all possibilities.
Second edit: I just realized I am completely wrong in what I'm saying below. Grover's algorithm is indeed optimal, and there is no equivalent classical algorithm that can finish as fast. However, this has nothing to do with BPP vs BQP, since it is not doing any kind of exponential speed up - both Grover's algorithm and classical search are polynomial time algorithms.
While this seems very likely, it has not yet been proven that unstructured search (the problem that Grover's algorithm solves) can't be solved by a probabilistic Turing machine in the same complexity with the same error bounds (that is, it's not proven that BPP != BQP).
So even if this seems intuitively obvious, it has eluded any proof so far - which I think is interesting in itself.
Edit: wording
While this seems very likely, it has not yet been proven that unstructured search (the problem that Grover's algorithm solves) can't be solved by a probabilistic Turing machine in the same complexity with the same error bounds (that is, it's not proven that BPP != BQP).
So even if this seems intuitively obvious, it has eluded any proof so far - which I think is interesting in itself.
Edit: wording
We are only talking about a polynomial speed up, so i dont think bqp vs bpp is relavent.
Yes, apologies, you are completely right and I amended my comment.
I think this is a likely outcome, and it's a reason why we should be continuing research into so-called "post-quantum" cryptosystems. Where there exists a low-cost quantum computing algorithm, it seems possible that there is a similarly low-cost probablistic algorithm.
Randomized and probablistic algorithms are in my opinion the most important area for future development in computer science. One hope is that the vocabulary and syntax of quantum computing can be used to create classical probablistic simulations directly that will result in solving all but the most combinatorially explosive cases of various problems.
Randomized and probablistic algorithms are in my opinion the most important area for future development in computer science. One hope is that the vocabulary and syntax of quantum computing can be used to create classical probablistic simulations directly that will result in solving all but the most combinatorially explosive cases of various problems.
No, it really does not seem like a likely outcome. There are way too many small "coincidences" that point to a substantial separation between complexity classes like BQP and BPP. On the other hand, it is indeed incredibly exciting to see all the progress in derandomization of classical probabilistic algorithms and de-quantization of some quantum algorithms (in particular, all the initial ideas in quantum machine learning).
Also, it seems most computational complexity theorists do not believe probabilistic algorithms (BPP) are more powerful than deterministic ones (P), and the details of this process of de-randomization are absolutely fascinating. E.g. how we found a deterministic prime-testing algorithm after decades of relying on the random ones. Or deterministic algorithms for creation of expander graphs. There is no equivalent to such derandomization techniques in the quantum case. Quantum and classical probabilities are just too different.
Also, post-quantum cryptosystems have very little to do with finding classical counterparts of quantum algorithms.
Also, it seems most computational complexity theorists do not believe probabilistic algorithms (BPP) are more powerful than deterministic ones (P), and the details of this process of de-randomization are absolutely fascinating. E.g. how we found a deterministic prime-testing algorithm after decades of relying on the random ones. Or deterministic algorithms for creation of expander graphs. There is no equivalent to such derandomization techniques in the quantum case. Quantum and classical probabilities are just too different.
Also, post-quantum cryptosystems have very little to do with finding classical counterparts of quantum algorithms.
I'm going to call this review maybe tight-lipped.
It does point to Intel's high-water marks: https://www.intel.com/content/www/us/en/research/quantum-com...
And to the nittier-grittier:
- https://www.nature.com/articles/s41928-022-00727-9 (300mm fab)
- https://meetings.aps.org/Meeting/MAR22/Session/M28.4 (cryoprober talk abstract)
- https://newsroom.intel.com/wp-content/uploads/sites/11/2020/... (which highlights that all of the key information regarding intel's work mentioned in this article was being presented in early December of 2020)
It does point to Intel's high-water marks: https://www.intel.com/content/www/us/en/research/quantum-com...
And to the nittier-grittier:
- https://www.nature.com/articles/s41928-022-00727-9 (300mm fab)
- https://meetings.aps.org/Meeting/MAR22/Session/M28.4 (cryoprober talk abstract)
- https://newsroom.intel.com/wp-content/uploads/sites/11/2020/... (which highlights that all of the key information regarding intel's work mentioned in this article was being presented in early December of 2020)
I dont know why quantum computers get so hyped. We are obviously still very far away from practically useful devices. We inch closer, but we are talking decades not years away.
Can we not get use out of them now though in data centers and as coprocessors for specialized devices?
No we cannot, and we are very far away from that point.
Eventually we probably will, but we are like 20 years away from that at least. And even if we can, its unclear how useful it would be except in very specialized situations.
Eventually we probably will, but we are like 20 years away from that at least. And even if we can, its unclear how useful it would be except in very specialized situations.
Right now, the most you could get from any existing QC in terms of practical every-day results is perhaps a good RNG - but there are far cheaper ones that are much more than good enough.
Otherwise, the state of the art is using existing QCs to find the prime factors of 21 with probability >66%.
The current huge value of QCs is in research into QC itself - we are very far from any practical applications.
Otherwise, the state of the art is using existing QCs to find the prime factors of 21 with probability >66%.
The current huge value of QCs is in research into QC itself - we are very far from any practical applications.
When I read about quantum computing I can't help but think of the talk given by D-wave founder Geordie Rose. He describes quantum computers as devices that perform calculations simultaneously across parallel universes.
https://www.youtube.com/watch?v=vlRVMNVXm3Q
https://www.youtube.com/watch?v=vlRVMNVXm3Q
> describes quantum computers as devices that perform calculations simultaneously across parallel universes
That's a completely valid interpretation shared by many physicists and quantum computer scientists. Media often misinterprets this to mean that the result is available instantly in one step, but actually we have to interfere those "worlds" to get the result with some algorithmic complexity that is unavoidable to quantum computers
That's a completely valid interpretation shared by many physicists and quantum computer scientists. Media often misinterprets this to mean that the result is available instantly in one step, but actually we have to interfere those "worlds" to get the result with some algorithmic complexity that is unavoidable to quantum computers
I don’t know of any physicist or CScientist who makes use of parallel universes in their thinking or publications. They may invoke the mystique to impress outsiders though.
D-wave’s claim to fame is a Quantum Annealer, and that term itself is misleading as quantum annealing is strictly speaking a classical algorithm (albeit quantum-inspired)
https://cs.stackexchange.com/questions/11218/the-physical-im...
https://cs.stackexchange.com/questions/11218/the-physical-im...
I’m an academic quantum computing guy, and the consensus in my quasilocal community is that D-wave is, appropriately for TFA, borderline fraudulent.
I think the correct title would technically be "Destructively interfering the hype from the facts of quantum computing"?
The algorithms that are touted as offering a pathway to quantum Supremacy, by Shor[1] and Grover[2] both rely on the Quantum Fourier Transform[3], which includes a large number of iterations through a Controlled Phase Shift Gate[4].
Those phase angles are crucial to the success of the QFT. Any error in the phase can not be corrected with current methods of Quantum Error Correction[5], which focus strictly on making sure that Qubits are in a "pure" state, essentially ignoring phase.
I thus include that Quantum Gate Computing is all hype.
The approach Dwave took, of quantum annealing[6], seems to offer some hope of real world performance surpassing that of conventional computing. However, there may be some algorithm out there that can do that annealing faster on conventional hardware. Also, there may be a way of using analog electronics to simulate annealing much faster than can be done currently in a program.
[1] https://en.wikipedia.org/wiki/Shor%27s_algorithm
[2] https://en.wikipedia.org/wiki/Grover%27s_algorithm
[3] https://en.wikipedia.org/wiki/Quantum_Fourier_transform
[4] https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift...
[5] https://en.wikipedia.org/wiki/Quantum_error_correction
[6] https://en.wikipedia.org/wiki/Quantum_annealing
Those phase angles are crucial to the success of the QFT. Any error in the phase can not be corrected with current methods of Quantum Error Correction[5], which focus strictly on making sure that Qubits are in a "pure" state, essentially ignoring phase.
I thus include that Quantum Gate Computing is all hype.
The approach Dwave took, of quantum annealing[6], seems to offer some hope of real world performance surpassing that of conventional computing. However, there may be some algorithm out there that can do that annealing faster on conventional hardware. Also, there may be a way of using analog electronics to simulate annealing much faster than can be done currently in a program.
[1] https://en.wikipedia.org/wiki/Shor%27s_algorithm
[2] https://en.wikipedia.org/wiki/Grover%27s_algorithm
[3] https://en.wikipedia.org/wiki/Quantum_Fourier_transform
[4] https://en.wikipedia.org/wiki/Quantum_logic_gate#Phase_shift...
[5] https://en.wikipedia.org/wiki/Quantum_error_correction
[6] https://en.wikipedia.org/wiki/Quantum_annealing
In a decent sized quantum Fourier transform, almost all of the phase gates are rotating by extremely tiny angles. For example, in a thousand qubit Fourier transform, 99% of the phase gates are rotating by an angle that is less than 0.000000000000000000000000001 degrees. That amount of rotation is irrelevant. You can skip 99.9% of the phase gates and the output will be de-facto indistinguishable from the ideal output. There's really a surprising amount of flexibility in the phasing.
Your second paragraph does not make much sense to me. Pretty much any quantum error correcting code being pursued today deals both with phase-flips and bit-flips. The comment about "pure" state also does not make much sense to me: a qubit afflicted by phase noise would not be in a pure state. I think you might be using the word "pure" in a way that is not the typical way it is used in the field.
Maybe you are trying to say that the more toy-like codes that have been demonstrated today, like the repetition code, do not protect against phase flips. That is true, these "easy" codes that are small enough for demonstrations on today's immature hardware indeed do not protect against all types of errors.
But codes like the toric code or qLDPC codes do protect both against phases errors and bit-flip errors. They are just too expensive to implement on today's immature hardware.
Lastly, no, Dwave's annealing approach is not particularly promising compared to others. Annealing does not provide real-world performance boost compared to classical computers unless you have error-corrected qubits.
Maybe you are trying to say that the more toy-like codes that have been demonstrated today, like the repetition code, do not protect against phase flips. That is true, these "easy" codes that are small enough for demonstrations on today's immature hardware indeed do not protect against all types of errors.
But codes like the toric code or qLDPC codes do protect both against phases errors and bit-flip errors. They are just too expensive to implement on today's immature hardware.
Lastly, no, Dwave's annealing approach is not particularly promising compared to others. Annealing does not provide real-world performance boost compared to classical computers unless you have error-corrected qubits.
I'm not talking about phase flips, but actual accumulated phase rotation due to noise, error, cross-talk, etc. Quantum error correction is geared towards keeping a Qubit in alignment with some axis through the Bloch sphere, at the two poles where it intersects the Bloch sphere. In order for the QFT to work, you have to be able to rotate around at least one axis, not near its poles.
I still do not understand. Quantum error correction does not require the qubit to be in a particular orientation on the Bloch sphere: any point on the Bloch sphere is equally protected. Are you saying that certain gates are simply difficult to perform precisely, e.g. that they will always have some systematic over-rotation? That also seems to be fixable with what is called randomized compiling.
Any point on the Bloch sphere can be protected... any discrete point, or set of points... but QFT and the rotations it depends upon are analog operations, not discrete.
No, all points are protected, not just some set. And no, you do not need infinite precision gates. The only reasonable interpretation of your argument that I can think of is that you are saying that systematic coherent errors add up in a way that error correction can not fix. That is a fascinating problem but it seems to be fixed by turning these errors into incoherent ones through "twirling" and "randomized compilation".
I hope you're right, it would be nice for QC to work out.
do you work on actual feasible implementation or just theoretical circuits for perfect mature qc?
I do basically zero work on "algorithms" or circuits for perfect quantum computers. The majority of my work is "here we have this noisy physical system, what can we do to it to make it look more like the abstract idea of a perfect quantum computer". I guess the classical equivalent would be "I am designing the internals of vacuum tubes".
This paper [1] claims that with their implementation they can get an AQFT (approximate QFT) with sufficient precision to factor RSA-2048 with < 0.01% error probability using 2083 qubits, 364,510 CNOT gates and 196,234 T gates, both of which can be error corrected.
[1] https://www.nature.com/articles/s41534-020-0257-5
Just because textbook QFT requires ever increasingly precise gates does not mean that this can't be worked around. If you want to do useful quantum computation you have to embrace error bounds, precision loss and probabilistic computing, which makes it quite difficult. But not impossible.
[1] https://www.nature.com/articles/s41534-020-0257-5
Just because textbook QFT requires ever increasingly precise gates does not mean that this can't be worked around. If you want to do useful quantum computation you have to embrace error bounds, precision loss and probabilistic computing, which makes it quite difficult. But not impossible.
I looked at their source code[1], which is indeed a listing of quantum gates, but no actual code that I could run. I'd be interested to see this run in simulation even on a very small N with realistic levels of errors.
[1] https://github.com/y-nam/QFT
[1] https://github.com/y-nam/QFT
[deleted]
It's 2022 and Shor's algorithm record on quantum computer is still only 21.
Facts and hyper are not entangled; they are conjugate.
The more you know the facts, the less room for hype. The more you're captured by hype, the less you're able to get to the facts.
The more you know the facts, the less room for hype. The more you're captured by hype, the less you're able to get to the facts.
There are plenty of challenges. In my eyes, the machines are going to require an exponential amount of precision. I don't have any proof, but that's what my instincts say.
It reminds me of why we use digital computers in the first place, there was a period in the 50's where the future of computing was unsure, was it going to be analog or digital?
digital won, mainly because the precision required for the components was far far lower. because of this a digital computer could be smaller faster and cheaper than it's analog version.
Makes me wonder if quantum computers are just the analog computers of our day.
digital won, mainly because the precision required for the components was far far lower. because of this a digital computer could be smaller faster and cheaper than it's analog version.
Makes me wonder if quantum computers are just the analog computers of our day.
This is a fundamental confusion borne of the historical accident that resulted in digital computers being called "computers" instead of "switches" or "controllers" or "logics" or "coders" or "analytical engines" or "programmable data processors" or something.
Analog "computers" are a totally different kind of thing. You can't run a compiler, solve an equation, play chess, or encrypt a message on an analog computer. It's not that they do those things slower or more expensively or in more space than digital "computers"; they just can't do them at all. (Except by simulating a digital computer, of course.)
We call computers "computers" because the first ones were built to do what analog "computers" do: numerical integration of ordinary differential equations, like Modelica does. (Eventually they were faster and cheaper than analog computers at that, but it took 20 years in many cases, and even today, we use analog circuits for things like RF downconversion.) But they can also do those other things.
In theory, the relationship with quantum computers is kind of similar. Quantum computers can in theory do anything a reversible classical digital computer can do in a similar number of operations, and also some other things (though probably not, say, solve SAT in polynomial time.) And classical digital computers can simulate QC, but as with simulating a digital computer on an analog one, the simulation is so inefficient as to be infeasible in all but trivial cases.
But maybe that's backwards? Does it depend on your efficiency metric? Certainly you need quite a lot of GPUs to approach the cost of a dilution refrigerator. We'll see.
Analog "computers" are a totally different kind of thing. You can't run a compiler, solve an equation, play chess, or encrypt a message on an analog computer. It's not that they do those things slower or more expensively or in more space than digital "computers"; they just can't do them at all. (Except by simulating a digital computer, of course.)
We call computers "computers" because the first ones were built to do what analog "computers" do: numerical integration of ordinary differential equations, like Modelica does. (Eventually they were faster and cheaper than analog computers at that, but it took 20 years in many cases, and even today, we use analog circuits for things like RF downconversion.) But they can also do those other things.
In theory, the relationship with quantum computers is kind of similar. Quantum computers can in theory do anything a reversible classical digital computer can do in a similar number of operations, and also some other things (though probably not, say, solve SAT in polynomial time.) And classical digital computers can simulate QC, but as with simulating a digital computer on an analog one, the simulation is so inefficient as to be infeasible in all but trivial cases.
But maybe that's backwards? Does it depend on your efficiency metric? Certainly you need quite a lot of GPUs to approach the cost of a dilution refrigerator. We'll see.
I suspect that if analog computers ever were developed to the point of being a universal computer(as opposed to the single case computers they were) the stored program and the interior operation would look a lot like what we call neural nets.
A bunch of linear algebra nodes interconnected with weighted feedback curves to govern operation.
A bunch of linear algebra nodes interconnected with weighted feedback curves to govern operation.
Universality is inherently digital.
Quantum computers are not analog computers. They are very much digital. A better analogy is with probabilistic computers: classical probabilistic computers are digital computers with a source of random bits. Quantum computers are digital computers in which randomness is governed by quantum probability amplitudes, not by classical probabilities. It is more fruitful to think of quantum computers as digital computers governed by a different, non-classical generalization of probability theory.
Have you seen Veritasium's analog revival video?
Some analog systems could be used as cheaper accelerators (like GPUs) for ML.
Some analog systems could be used as cheaper accelerators (like GPUs) for ML.
Even if this were the case it’d be a tech-tree issue and that’s all. We couldn’t built modern processors without classical computers either but we don’t say we shouldn’t do that.
Imo modern classical Processors are a temporary solution that will eventually replace itself with a diverse array of computational architectures that fit different purposes and use cases.
Imo modern classical Processors are a temporary solution that will eventually replace itself with a diverse array of computational architectures that fit different purposes and use cases.
>Over the past five years, there has been undeniable hype around quantum computing—hype around approaches, timelines, applications, and more. As far back as 2017, vendors were claiming the commercialization of the technology was just a couple of years away—like the announcement of a 5,000-qubit system by 2020 (which didn’t happen).
Inaccurate. D-Wave did in fact launch a 5000+ qubit system named Advantage in 2020.
Inaccurate. D-Wave did in fact launch a 5000+ qubit system named Advantage in 2020.
Here's the real question to those of you who don't believe in quantum computing - what do you think that money should be invested in instead? VCs are supposed to try to maximize their returns in high-risk high-reward investments using their knowledge of technology to get an advantage. It doesn't seem like to me there are that many opportunities that aren't already saturated with cash. If quantum computing has a 10% chance of paying out, that's equivalent to the success rate of startups (on average).