It seems most of these types of post are about simulated quantum effects which end up being faster to do with quantum computers than with classical computers.
However, that kind of feels to me like saying my analog computer (which consists of my hand, a floor, and a glass) can simulate a glass falling, hitting the floor, and shattering faster than a classical computer.
I think that's a fair description of the achievements made so far, but there are some quantum simulations that would be worthwhile or even groundbreaking to simulate (and it's possible that quantum computing is the only way to handle large quantum simulations). My guess is that we're a ways off from them, and even further off from any impressive integer factorizing/cryptography breaking quantum computers (but those predictions are basically worthless).
I'm definitely not an expert in the field, but I read lecture notes by Scott Aarsonson that referenced research by Microsoft that looked into nitrogen fixation specifically as a (potentially) achievable simulation with a (potentially) massive impact.
At one time, an electronic analog computer would have simulated that faster than an electronic digital computer. Not sure where that falls in this argument — are analog computers “classical”?
“A Facebook friend said to me: that’s well and good, but surely we could change Borcherds’s teapot experiment to address this worry? For example: add a computer-controlled lathe (or even a 3D printer), with which you can build a teapot in an arbitrary shape of your choice. Then consider the problem of sampling from the probability distribution over how many pieces that teapot will smash into, when it’s dropped from some standard height onto some standard surface. I replied that this is indeed more interesting—in fact, it already seems more like what engineers do in practice (still, sometimes!) when building wind tunnels, than like a silly reductio ad absurdum of quantum supremacy experiments. On the other hand, if you believe the Extended Church-Turing Thesis, then as long as your analog computer is governed by classical physics, it’s presumably inherently limited to an Avogadro’s number type speedup over a standard digital computer, whereas with a quantum computer, you’re limited only by the exponential dimensionality of Hilbert space, which seems more interesting.”
Funny thing is, a "perfect and noiseless" analog computer is actually more powerful than a digital quantum computer. It is just that you can not make a noiseless analog computer -- we know how to perform "error correction" only on digital computers. Basically, in our history we have:
- real noisy analog computers which are easiest to build, fast for their restricted small problems, but they are not programmable and they are not scalable (because the moment they become "big", the noise becomes too problematic and swamps the results)
- error-corrected digital computers that are programmable and scalable
- today we have small, noisy, quantum hardware that is halfway between a quantum analog computer (i.e. a fun physics experiment) and some actual digital quantum computing machine. Great engineering achievement, but not yet what was promised by the field
- hopefully, soon enough we will have scalable error-corrected "digital" quantum computers. They will be programmable and error-corrected which is the big distinction between them and a fun single-purpose physics experiment
Yet another task that's essentially a simulation of a specific physical phenomenon, not demonstrating an advantage on any generic computing task.
As the article states, it's 216 qubits; far too small to do anything faster than a calculator for the quantum algorithms that we do care about (e.g. factoring prime numbers, searching, etc) - after all, running a 256-qubit quantum task on a 216-qubit quantum computer effectively incurs a 2^40 slowdown.
I believe we had publications of multiple other similar scale (200-ish qubit) systems before, and it's progress if and only if the particular physical process (there are many very different, effectively unrelated physical processes which have been used to build quantum computers - many of these other quantum computing systems have little in common) can scale to 100x more qubits without succumbing to noise that destroys coherence. Perhaps this one has this potential, I can't judge that, but they don't seem to be asserting it.
It's only trivial if you already know it's prime. Determining that is non-trivial enough that a tractable deterministic algorithm wasn't devised until 2002, and its time complexity is thought to be the sixth power of log(n = digits).
Xanadu's main thing is that they are really good at getting money from Canadian VCs and government.
They often make insane claims like: https://arxiv.org/abs/1810.10644
I'd take anything coming from them with a grain of salt.
https://en.wikipedia.org/wiki/Boson_sampling
boson sampling was introduced for quantum supremacy experiments.
it does not have any practical applications and it's supposed to be easy for QCs.
Well the guys at Xanadu believe that for some bizarre reason it can be used to solve all sort of useful problems.
Exactly. To use an analogy from simulation - as I understand it - one can do a very detailed finite element analysis of a component using hours of computing time to determine its failure mode -- or you can stress it until it breaks, and get your answer in a few seconds. That does not mean that breaking things is a good method to solve general problems; it is just very well suited for this specific problem.
I do not think this is a good example. You and OP are making two orthogonal points (both of which are good, but not both apply to Bosonic Sampling).
1. You were making an argument about analog computers. There is big difference between a digital computer and an analog simulator. See this comics https://www.smbc-comics.com/comic/2013-07-19 -- We have went through this with classical computers over the last 100 years. The first computers were analog simulators that were just rescaled physical experiments: instead of measuring the flow of a river you made a scale model; instead of measuring the trajectory of a bomb you made an analog electronic model. These computers were great time-savers, but they were single-purpose and not "scalable" (i.e. the precision of their results was very limited due to fundamental physical reasons). When digital computers become sophisticated enough, we stopped using analog computers: a digital fluid model of the river is better than an analog scale model because by "just" increasing the mesh resolution you get more precise results, infeasible in the analog case; the digital bomb trajectory simulator is better because by "just" adding a new term and changing a data type you get more realistic results. Basically, digital computers are (a) scalable and (b) reprogrammable. Analog computers are not -- they are just rescaled physical experiments. Much of quantum computation today is just that: an analog experiment too far from the digital regime.
2. The point that OP was making is that Boson sampling, while it can be considered "digital" and "programmable" is too "boring". It shows a computation that can not be done by a classical computer efficiently, but the computation itself is just some silly sampling problem from a probability distribution that we would probably never care about. However, to me at least, it is a very big deal that we can reprogram (change the parameters) on the fly the probability distribution. And it is an even bigger deal that this is a scalable computation: a simple analog computer just starts giving chaotic results when you add too many degrees of freedom, unlike here where you start sampling from even more complicated distributions.
If anything that paper looks really cool (not that I understand it). Transforming classical problems like graph isomorphism into a quantum algorithm is legit science and potentially extremely valuable.
Did they actually find a quantum algorithm for graph isomorphism? I was under the impression that was a major unsolved problem and would be a pretty big deal.
If the Canadian government suddenly grows some skepticism, they can just take the money and continue to shovel more funds at Telesat, which is now about 7 years behind schedule on its starlink-competitor LEO network.
How does anyone launch satellites? You pay someone to do it. Are you under the impression you need to have a rocket company to do this? One of the mandates of SpaceX (and others) is to lower the cost of these things.
Isn't this really just observing a quantum system that would extremely expensive to compute?
Let me give an analogy: protein folding. Proteins can be very large consisting of thousands of atoms. Because of the movement of electrons and the electrical and magnetic effects you get, it's difficult to compute the shape of a given molecule. In recent years a ton of progress has been made on this to be clear.
But my point is this: I could construct a protein and then determine its structure experimentally and call that a quantum computer but have I really computed anything? Side note: yes I know some proteins have defied traditional mapping techniques like X-ray diffraction; that's beside the point.
Another thought: large classical systems don't exhibit quantum behaviour. Small so-called quantum systems do. I'm talking things like superposition and entanglement. It's unclear where the boundary between the classical and the quantum actually is or if there even is one.
But information is physical [1] and there are physical limits on how much ifnrmation a system can hold and consequently how much computation a system can perform.
I don't expect quantum computers to be able to "break" this limit as some suggest by merely addin gmore qubits. But who can really say?
Yes but most of the time the compute abstractions are reasonably accurate that a slight loss of fidelity is still magnitudes better than physical experimentation. For example if you want to build a Boston dynamics style robotic dog, a kinematics simulator coupled with a CAD tool can get you a long way cheaply versus having to build hundreds of prototypes.
A computer is broken up into small discrete steps where error correction can happen. The essential idea is that the logical space of the computer is a suitably "discrete" set of points in the actual phase space of the system on which it is embdedded. By discrete, I mean that there is some radius around each valid point of the phase space, such that the collection of all of the balls of that radius around the valid points are still disjoint. I have a special operator that I then use to map each ball down to its corresponding point called a projection (Invoking this operator requires me to generate waste heat, see Landauer's principle. Also, in reality, I do not have points. I have small regions contained in larger regions).
I then generate a system of computational primitives which reliably map the small regions inside of these larger regions, with the result that I can perform projection, computation, projection, and be reasonably certain that my process deterministic acts on the small regions, without knowing anything about the particular computation that I have performed except that it was made out of the primitives.
This projection gets performed after every computational step, and is the thing that separates a digital computer from an analog computer. It is also a thing that separates digital computers from quantum computers, except that the physicists (in my mind incorrectly) believe that they have a scheme which can perform the error correction without damaging the logical state, and can use this scheme to produce a high enough fidelity state at the start that the whole program can be run without loss of coherence.
His explanation is kind of the high-fidelity version of the first day of digital electronics class. Digital computation relies on voltage levels that are high or low. The voltage level of the output of a step is not directly related to the voltage of the input, just whether that voltage falls in the low range or the high range. This fact prevents inexact voltage from compounding over time. Maybe you're using 3.3v logic; one step's input could be 3.2v and that would still be a high, and the output, if high, might be 3.5v. Non-digital systems don't inherently have that constant resetting of levels back to discrete values like digital systems do.
I had a lot of finals, and the answer to this comment that I did not write was essentially accurate. The people who think about computers this way are the people who have to implement them on analog devices, aka the electrical engineers. There is a discrete analog (lol) in the form of coding theory, since it often more practical to make a slightly noisy discrete space and then perform discrete error correction.
I was looking at your other comments to see how I should answer you, and I gathered that I can just link you papers. I imagine Von neumann and Hamming and shannon all have something to say about this topic, but since we're talking about quantum computing, I believe the relevant work can be found in these, and their references.
I think there's been a fair amount of discussion about the interplay between quantum and classical computing. It feels like it may be better to think of things as a collaborative environment in that algorithms found via quantum computing can lead to improvements in their classical counterparts.
the important thing imo isn't the distinction of computing vs running experiment/simulating, but rather the pragmatical aspects around it: how easy is it to set up and execute.
if a quantum processor is sufficiently similar to regular computers and you can just run a couple of lines of code to actually simulate an arbitrary variety of different quantum systems, that will have mind boggling implications for large aspects of technology that deal with quantum systems (like material science).
But the fraction of computing that deals with quantum systems is a tiny. I would like to see performance on a more neutral benchmark than Gaussian boson sampling. I mean, it's fine to include boson sampling but it would be nice to see QC performance on general hard problems improve over time as well.
Or to dumb down your analogy even more, isn’t it just like observing a random particle system and then saying well a supercomputer couldn’t compute that?
That would make them collapse into a single one. Note it would have nothing to do with quantum mechanics, it'd simply be the OOM-killer making a choice.
Symmetric crypto you can increase the key size. e.g. AES128 would be insecure (as it would drop to 64bits of security), but AES256 wouldn't (it would still provide 128 bits of security).
I believe there is also quantum resistant asymmetric crypto schemes too (lattice based schemes) ?
After reading the article I still don't know what the Quantum computer DID exactly. What did it compute? What question asked and answered?
All I got was "benchmark". But my benchmark of "smashing monitors with a hammer" says my hands beat any quantum computer so I am disinclined to believe the usefulness of a benchmark.
Quantum computing news seems on par with fusion. The actual field may indeed progressing but nothing useful yet.
"We carry out Gaussian boson sampling (GBS) on 216 squeezed modes entangled with three-dimensional connectivity5, using a time-multiplexed and photon-number-resolving architecture. On average, it would take more than 9,000 years for the best available algorithms and supercomputers to produce, using exact methods, a single sample from the programmed distribution, whereas Borealis requires only 36 μs."
> When given the same problem, a quantum computer should be able to trounce any supercomputer in any problem in terms of speed and efficiency
LOL, no, not any problem, far from it. Some problems, rather specific ones, such as prime factoring.
> Our current system, for example, taps into electrons and cleverly-designed chips to perform their functions. Quantum computers are similar, but they rely on alternative particle physics.
Um, no, they both rely on the same physics, that is a combination of Quantum Mechanics and electromagnetism. Note to the author: an electron is a quantum system, and classical electronics definitely rely on that.
So yes, quantum computers are overhyped, through no faults of their own, and this article contributes to the trend.
Yes it's overhyped, but to be fair, the whole point of classical electronics is to hide the quantum nature as much as possible. You want your transistor to act as a deterministic switch, not be in a superposition of states.
Well, to be also fair, we also want quantum electronics to be deterministic in their behaviour. The difference lies not so much in randomness as in leveraging intrication.
> LOL, no, not any problem, far from it. Some problems, rather specific ones, such as prime factoring.
Yeah, as someone who works in quantum computing this is the hardest thing for me to explain to non-technical people. For technical people, I liken it to a FP unit or some other specialized coprocessor that's often embedded in CPU/GPUs.
> Quantum computers are similar, but they rely on alternative particle physics.
I think it's fair to say this in reference to using different physical properties of electrons than what normal computers use. The physics rules are the same, but how you manipulate them is different, presumably (I don't know much of how photonic QCs work)
I never thought of it that way for some reason. Always imagined mature quantum computers as being their own system. But it's possible a lot of them will be supplementary components to a classical computer. We have storage-over-PCIe, graphics-over-PCIe, and soon quantum-over-PCIe?
It'll be a long time before they need remotely comparable bandwidth, and more than likely the latency on higher level protocols won't even be near. PCIe would work fine, but so would old school serial.
That seems unlikely to happen in the near to medium term. For that to happen, everything would have to be rewritten using a quantum algorithm and language, and run on quantum hardware. Imagine writing a web browser in a quantum language, within a quantum computing software ecosystem. It's hard to see how that would have any benefit.
If you are talking 100 years out, though, who knows?
I made the same remark in reply to another comment which used the phrase "factoring primes" :) Wikipedia does use the term "prime factorization": that seems legit to me, as prime is used as an adjective. https://en.wikipedia.org/wiki/Integer_factorization
Another legitimate meaning might be "factoring probable primes" (or "candidate primes" as they are sometimes called in key generation/cryptanalysis), or possibly "factoring semiprimes".
Both of those phrases could be referred to as "prime factorisation" in a not-entirely-accurate-but-unambiguous-in-context shorthand.
> Some problems, rather specific ones, such as prime factoring.
This is absolutely how we understand the technology now, but I think it's worth noting that computing luminaries also thought "640Kb of memory was more than enough for anyone" and that "eight mainframe computers will serve the computing needs of everyone across the planet" at one point in time, too. Quantum computers are definitely overhyped and that may be all they're good for, but it's also possible we'll figure out how to do some crazy shit with them in the future, too.
72 comments
[ 3.0 ms ] story [ 132 ms ] threadHowever, that kind of feels to me like saying my analog computer (which consists of my hand, a floor, and a glass) can simulate a glass falling, hitting the floor, and shattering faster than a classical computer.
I'm definitely not an expert in the field, but I read lecture notes by Scott Aarsonson that referenced research by Microsoft that looked into nitrogen fixation specifically as a (potentially) achievable simulation with a (potentially) massive impact.
https://www.scottaaronson.com/qclec/29.pdf
https://www.microsoft.com/en-us/research/wp-content/uploads/...
“A Facebook friend said to me: that’s well and good, but surely we could change Borcherds’s teapot experiment to address this worry? For example: add a computer-controlled lathe (or even a 3D printer), with which you can build a teapot in an arbitrary shape of your choice. Then consider the problem of sampling from the probability distribution over how many pieces that teapot will smash into, when it’s dropped from some standard height onto some standard surface. I replied that this is indeed more interesting—in fact, it already seems more like what engineers do in practice (still, sometimes!) when building wind tunnels, than like a silly reductio ad absurdum of quantum supremacy experiments. On the other hand, if you believe the Extended Church-Turing Thesis, then as long as your analog computer is governed by classical physics, it’s presumably inherently limited to an Avogadro’s number type speedup over a standard digital computer, whereas with a quantum computer, you’re limited only by the exponential dimensionality of Hilbert space, which seems more interesting.”
https://scottaaronson.blog/?p=5460 (“Doubts about teapot supremacy: my reply to Richard Borcherds”)
- real noisy analog computers which are easiest to build, fast for their restricted small problems, but they are not programmable and they are not scalable (because the moment they become "big", the noise becomes too problematic and swamps the results)
- error-corrected digital computers that are programmable and scalable
- today we have small, noisy, quantum hardware that is halfway between a quantum analog computer (i.e. a fun physics experiment) and some actual digital quantum computing machine. Great engineering achievement, but not yet what was promised by the field
- hopefully, soon enough we will have scalable error-corrected "digital" quantum computers. They will be programmable and error-corrected which is the big distinction between them and a fun single-purpose physics experiment
As the article states, it's 216 qubits; far too small to do anything faster than a calculator for the quantum algorithms that we do care about (e.g. factoring prime numbers, searching, etc) - after all, running a 256-qubit quantum task on a 216-qubit quantum computer effectively incurs a 2^40 slowdown.
factoring into prime numbers ;-) (factoring a prime number is trivial, that's why it's called prime)
I'd take anything coming from them with a grain of salt.
1. You were making an argument about analog computers. There is big difference between a digital computer and an analog simulator. See this comics https://www.smbc-comics.com/comic/2013-07-19 -- We have went through this with classical computers over the last 100 years. The first computers were analog simulators that were just rescaled physical experiments: instead of measuring the flow of a river you made a scale model; instead of measuring the trajectory of a bomb you made an analog electronic model. These computers were great time-savers, but they were single-purpose and not "scalable" (i.e. the precision of their results was very limited due to fundamental physical reasons). When digital computers become sophisticated enough, we stopped using analog computers: a digital fluid model of the river is better than an analog scale model because by "just" increasing the mesh resolution you get more precise results, infeasible in the analog case; the digital bomb trajectory simulator is better because by "just" adding a new term and changing a data type you get more realistic results. Basically, digital computers are (a) scalable and (b) reprogrammable. Analog computers are not -- they are just rescaled physical experiments. Much of quantum computation today is just that: an analog experiment too far from the digital regime.
2. The point that OP was making is that Boson sampling, while it can be considered "digital" and "programmable" is too "boring". It shows a computation that can not be done by a classical computer efficiently, but the computation itself is just some silly sampling problem from a probability distribution that we would probably never care about. However, to me at least, it is a very big deal that we can reprogram (change the parameters) on the fly the probability distribution. And it is an even bigger deal that this is a scalable computation: a simple analog computer just starts giving chaotic results when you add too many degrees of freedom, unlike here where you start sampling from even more complicated distributions.
I have my doubts...
Not sure what the key paper is, but "Graph isomorphism in quasipolynomial time" is at leas relevant:
https://dl.acm.org/doi/10.1145/2897518.2897542
or perhaps, this arxiv paper:
https://arxiv.org/abs/1512.03547
No idea about a quantum algorithm for GI
How does anyone launch satellites? You pay someone to do it. Are you under the impression you need to have a rocket company to do this? One of the mandates of SpaceX (and others) is to lower the cost of these things.
Let me give an analogy: protein folding. Proteins can be very large consisting of thousands of atoms. Because of the movement of electrons and the electrical and magnetic effects you get, it's difficult to compute the shape of a given molecule. In recent years a ton of progress has been made on this to be clear.
But my point is this: I could construct a protein and then determine its structure experimentally and call that a quantum computer but have I really computed anything? Side note: yes I know some proteins have defied traditional mapping techniques like X-ray diffraction; that's beside the point.
Another thought: large classical systems don't exhibit quantum behaviour. Small so-called quantum systems do. I'm talking things like superposition and entanglement. It's unclear where the boundary between the classical and the quantum actually is or if there even is one.
But information is physical [1] and there are physical limits on how much ifnrmation a system can hold and consequently how much computation a system can perform.
I don't expect quantum computers to be able to "break" this limit as some suggest by merely addin gmore qubits. But who can really say?
[1]: http://greenbyte.ch/wp-content/uploads/2015/03/Landauer_1991...
I then generate a system of computational primitives which reliably map the small regions inside of these larger regions, with the result that I can perform projection, computation, projection, and be reasonably certain that my process deterministic acts on the small regions, without knowing anything about the particular computation that I have performed except that it was made out of the primitives.
This projection gets performed after every computational step, and is the thing that separates a digital computer from an analog computer. It is also a thing that separates digital computers from quantum computers, except that the physicists (in my mind incorrectly) believe that they have a scheme which can perform the error correction without damaging the logical state, and can use this scheme to produce a high enough fidelity state at the start that the whole program can be run without loss of coherence.
I was looking at your other comments to see how I should answer you, and I gathered that I can just link you papers. I imagine Von neumann and Hamming and shannon all have something to say about this topic, but since we're talking about quantum computing, I believe the relevant work can be found in these, and their references.
https://arxiv.org/abs/quant-ph/9705052
https://arxiv.org/abs/quant-ph/0403025
I'll check back on this thread if you have questions. If I had all of the answers to my own questions though, I would be famous.
Sure — but we’re not anywhere near that limit.
Also, you can entangle remote quantum systems which is a different paradigm for distributed computing than you can do with a classical computer.
With classical computers, you get a summation of joining the two systems; with quantum computers, you get the product of joining the two systems.
https://physics.aps.org/articles/v15/19 as an example.
if a quantum processor is sufficiently similar to regular computers and you can just run a couple of lines of code to actually simulate an arbitrary variety of different quantum systems, that will have mind boggling implications for large aspects of technology that deal with quantum systems (like material science).
But make sure not to look at them.
That would make them collapse into a single one. Note it would have nothing to do with quantum mechanics, it'd simply be the OOM-killer making a choice.
Symmetric crypto you can increase the key size. e.g. AES128 would be insecure (as it would drop to 64bits of security), but AES256 wouldn't (it would still provide 128 bits of security).
I believe there is also quantum resistant asymmetric crypto schemes too (lattice based schemes) ?
All I got was "benchmark". But my benchmark of "smashing monitors with a hammer" says my hands beat any quantum computer so I am disinclined to believe the usefulness of a benchmark.
Quantum computing news seems on par with fusion. The actual field may indeed progressing but nothing useful yet.
Well, let's see:
> When given the same problem, a quantum computer should be able to trounce any supercomputer in any problem in terms of speed and efficiency
LOL, no, not any problem, far from it. Some problems, rather specific ones, such as prime factoring.
> Our current system, for example, taps into electrons and cleverly-designed chips to perform their functions. Quantum computers are similar, but they rely on alternative particle physics.
Um, no, they both rely on the same physics, that is a combination of Quantum Mechanics and electromagnetism. Note to the author: an electron is a quantum system, and classical electronics definitely rely on that.
So yes, quantum computers are overhyped, through no faults of their own, and this article contributes to the trend.
Yeah, as someone who works in quantum computing this is the hardest thing for me to explain to non-technical people. For technical people, I liken it to a FP unit or some other specialized coprocessor that's often embedded in CPU/GPUs.
> Quantum computers are similar, but they rely on alternative particle physics.
I think it's fair to say this in reference to using different physical properties of electrons than what normal computers use. The physics rules are the same, but how you manipulate them is different, presumably (I don't know much of how photonic QCs work)
If you are talking 100 years out, though, who knows?
You don't need a quantum computer for that! I can factor arbitrarily large primes in my head. For any given prime p, it's factors are 1 and p. Done!
:-)
Both of those phrases could be referred to as "prime factorisation" in a not-entirely-accurate-but-unambiguous-in-context shorthand.
https://en.wikipedia.org/wiki/Probable_prime
https://en.wikipedia.org/wiki/Semiprime
This is absolutely how we understand the technology now, but I think it's worth noting that computing luminaries also thought "640Kb of memory was more than enough for anyone" and that "eight mainframe computers will serve the computing needs of everyone across the planet" at one point in time, too. Quantum computers are definitely overhyped and that may be all they're good for, but it's also possible we'll figure out how to do some crazy shit with them in the future, too.