Disentangling the facts from the hype of quantum computing
spectrum.ieee.org
spectrum.ieee.org
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).
Getting that architecture down is worth web3, even if none of the platforms and services continue on.
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.
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.
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.
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)
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.
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.
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.
> 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.
Really? I wasn't aware science told us what was real.
It's called the "Copenhagen interpretation" for a reason.
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?
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.)
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.
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.
This comment really sounds like: "why go to Mars, we haven't even explored our own oceans". As if those are somehow mutually exclusive.
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.
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.
"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.
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
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.
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.)
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.
> 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
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.
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.
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...
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.
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.
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.
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
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.
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)
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.
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.
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
https://cs.stackexchange.com/questions/11218/the-physical-im...
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...
[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.
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.
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.
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.
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.
A bunch of linear algebra nodes interconnected with weighted feedback curves to govern operation.
Some analog systems could be used as cheaper accelerators (like GPUs) for ML.
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.
Inaccurate. D-Wave did in fact launch a 5000+ qubit system named Advantage in 2020.