The Era of Quantum Computing Is Here. Outlook: Cloudy
quantamagazine.org
quantamagazine.org
I'm really glad to find they did not go for these usual pieces of pop-explanations, and even called them out as not really capturing the essence of quantum computing. It takes courage to not hide behind these inaccurate descriptions, and instead just give the unsatisfying truth that there's no simple layman level description beyond "quantum mechanics somehow creates a “resource” for computation that is unavailable to classical devices"; at least not with today's easily available mental models[1] we have from classical computing.
[1] http://lesswrong.com/lw/kg/expecting_short_inferential_dista...
There are parts of the comic that I don't even begin to understand (I honestly couldn't tell you if hilbert space is even a real thing, and I don't even want to being to think about how or why amplitudes can be complex, and what you would possibly do with a complex probability...), but the whole idea of amplitudes being loosely analogous to probabilities,and how interference is the real "secret sauce" that allows quantum computers to gain a big advantage in some problems is what it finally made click for me. And it kind of got across the point that the real difficulty with quantum computing is going to be in isolating these "qbits" from the world (which made the originally linked article much easier to read).
I've also attempted to read a bunch about it from many different sources before this, so I had some primer on some of the ideas behind it, but couldn't understand how the parts fit together, or why they were such a big deal (often flip-flopping between the 2 feelings depending on the metaphors the last thing I read used).
If quantum computers ever become "mainstream", I think we will need to start teaching the basics behind them in schools, because there isn't an easy way to map the ideas there to classical ones.
I think of it like imagine trying to explain how a CPU works to a person that doesn't know basic math. There is no way to even "ELI5" that, there just isn't enough of a foundation to work from, and any attempt to do so would take so many liberties that it wouldn't even really be useful. Right now quantum computing seems extremely difficult to even understand the basics because 99.99%+ of us are missing those foundations.
I don't pretend to completely understand it either, but one crucial point here is that these complex amplitudes and their interactions are the "real" reality - they are "more real" than the normal probabilities we are used to, in that they are the things that actually exist in the universe and give rise to the 'normal' probabilities that we see.
A lot of mental resistance to quantum mechanical ideas comes from thinking quantum mechanics is weird, instead of thinking quantum mechanics as normal and us being weird[1], because of the scale we live in and normally observe things in.
[1] paraphrased from Eliezer Yudkowsky, Harry Potter and the Methods of Rationality, Ch 36
[0] https://parahumans.wordpress.com/ [1] http://unsongbook.com/
Reality has been around since long before you showed up. Don't go calling it nasty names like "bizarre" or "incredible". The universe was propagating complex amplitudes through configuration space for ten billion years before life ever emerged on Earth. Quantum physics is not "weird". You are weird. You have the absolutely bizarre idea that reality ought to consist of little billiard balls bopping around, when in fact reality is a perfectly normal cloud of complex amplitude in configuration space. This is your problem, not reality's, and you are the one who needs to change.
http://lesswrong.com/lw/hs/think_like_reality/
(Really, a lot of insights in HPMOR are just reiterations of points Eliezer made in his Sequences.)
Probability amplitudes are something we don’t really understand, but it is true that once we have set a basis for measurement, we can treat the amplitudes with respect to that basis as probabilities (written in complex form).
However, this should not be interpreted as “quantum states are probabilistic mixtures of base states” - changing the measurement basis screws up that intuition. For example, if our new basis has one base vector that is equal to the quantum state we are measuring, suddenly our outcome is certain.
Oh I wish I could explain this better.
Out of my many questions (for which I should probably seek books and videos), I'll ask this one:
> changing the measurement basis screws up that intuition. For example, if our new basis has one base vector that is equal to the quantum state we are measuring, suddenly our outcome is certain.
How does one change the measurement basis - is it a mathematical exercise done on paper, or is it an actual physical act?
Is this what is meant by collapse of a wave function?
Is this what we are doing when we 'measure' Schrodinger's cat at the end of the experiment and suddenly have a certain outcome?
Measurement is indeed wave function collapse - when a quantum state in a superposition (with regards to our measurement basis) is measured and produces a definite answer.
Although this one won't make any sense unless you read a lot of these kinds of webcomics!
The Kid : Wait, you guys put complex numbers in your ontologies?
The Mom: We do and we enjoy it.
The Kid : Ewww
He also rejects the idea that there's something ineffable about quantum mechanics, or that the reason quantum computation works can't be explained using ordinary logic and reasoning that is accessible in principle to everybody (I don't know for sure that's what is meant here by "somehow creates a “resource”": but I'm triggered a bit by those words because people often do essentially mean that).
Of course he would (correctly) say that one shouldn't treat him as being an infallible source of truth on the matter. But he does believe that the purpose of science is to explain the world, which puts him in a different class from apologists for quantum mysticism, strict empiricism and other believers in explanation-free knowledge.
There are a couple neat videos about the tech. [1,2] You can access the service through a Python API [3].
Disclaimer: I work there.
[1] “Lisp at the Frontier of Computation” https://youtu.be/f9vRcSAneiw
[2] Rigetti talk at QIP 2017 https://youtu.be/IpoASc18P5Q
From my reading most crytographers think it's is secure. So if you need it now. You could probably get away with using it. However, one should have a decent explanation to why use a less well known algorithm. It's probably had less eyes looking at so a major flaw/attack could exists, but it's not if one does exist.
The real issue, as you touched on, is key size. There are production deployments of the cryptosystem, but it’s actually a bit worse than your numbers if you’re looking for post-quantum resistance. In the post-quantum secure setting, McEliece uses public keys that have an upper bound of over 1MB (around 8.5 million bites specifically) in order to achieve 128-bit security.
Fortunatly McEliece is not the only proposal we have, and error correcting codes aren’t the only computational problem being studied. We also have credible proposals from lattices, hashes, multivariate polynomial equations and (most recently) supersingular elliptic curve isogenies.
For proprietary protocols the "newiness" of pq-crypto doesn't seem to be a big problem per se, just use curve hardening (kdf(ECDH || pq-kex)) in case the pq-crypto is broken (either due to implementation defects or cryptanalysis).
And yes - SIDH is also attractive because of the small key sizes. But it’s also significantly slower than lattice-based key exchange using something like Learning With Errors (LWE). In practice the decision comes down to time versus space constraints: if your application is space-poor and time-rich, SIDH is a good proposal for key exchange. This looks especially nice in the context of IoT devices. But if your application is space-rich and time-poor, SIDH looks less attractive in favor of other options.
Contemporary research is predominantly concerned with improving computability efficiency or security proofs for underlying complexity characteristics.
That's what I meant above; I apologize for I should have been more clear in my wording.
In other words, for some lattice problems, we can prove that breaking the cryptosystem is equivalent to breaking every instance of the lattice problem, but factoring problems only guarantee that breaking the cryptosystem is equivalent to breaking a subset of problems from some distibution. The former is a much stronger security assumption (though in practice this comes with its own set of challenges).
It’s an exciting area of research.
I think quantum computers will be useful for some applications (maybe even many) and commercially available within the next decade or two, I just don’t think cryptographic breaks will be possible on them until they advance well beyond whatever is first brought to market. You need logical qubits for polynomial-time cryptanalysis of RSA, and many of them. To get these logical qubits, you need so many more physical qubits that it’s not really productive to map our current records (~50 qubits) to what we’d need. In fact, I predict we’ll get to quantum cryptanalysis via a paradigm shift that approaches the problem in a fundamentally different way long before we master the requisite error correction to have enough physical and logical qubits necessary under the current paradigm.
[1] https://en.wikipedia.org/wiki/Timeline_of_quantum_computing
https://media.vw.com/releases/951
IBM is also giving select customers access to its real 17-qubit quantum computer.
https://arxiv.org/abs/1801.00862
This is a write up of his keynote talk at Q2b this year.
As the article points out, noisy quantum computers won't be useless. They could be used to speed up some optimization and quantum chemistry tasks.
But again the alternatives are basically just representing your qubits as huge vectors and gates as huge matrices and just doing lots of multiplication, which is an extremely cumbersome and frustrating way to program and precludes any kind of abstraction, even for toy learning problems.
Some researchers think that the problem of error correction will prove intractable and will prevent quantum computers from achieving the grand goals predicted for them.
The author then provides a quote intending to justify this claim, but the quoted mathematician merely points out the difficulty of error correction (by--correctly--pointing out that quantum error correction is more difficult than merely proving quantum supremacy, i.e. producing a quantum result that cannot be accurately be replicated using a classical computer), and doesn't say the problem of error correction will prove intractable.
The author seems to be painting a picture of quantum computing that is less certain than is warranted. A counter-point to the popular hype of quantum computing is necessary, but it shouldn't include such inaccuracies.
Are quantum computers just the fusion reactors of the computing world? Maybe one won't be built for 20 or 30 years, maybe longer.
I'm not talking about the pop science articles you read who find the most outlandish quote they can find. (There are plenty of those now that say 1-3 years.) I'm talking about what the actual typical practitioner says.
This is not the proper take-away message from the history of fusion. The expert consensus in 1976 predicted that useful fusion would not be achieved if it followed the funding trajectory it actually did end up taking.
> While the energies of molecular hydrogen can be computed classically (albeit inefficiently), as one scales up quantum hardware it becomes possible to simulate even larger chemical systems, including classically intractable ones. For instance, with only about a hundred reliable quantum bits one could model the process by which bacteria produce fertilizer at room temperature. Elucidating this mechanism is a famous open problem in chemistry because the way humans produce fertilizer is extremely inefficient and consumes 1-2% of the world's energy annually. Such calculations could also assist with breakthroughs in fundamental science, for instance, in the understanding of high temperature superconductivity.
https://research.googleblog.com/2016/07/towards-exact-quantu...
Factoring small numbers is a "very simple calculation," and it has been done multiple times with quantum computers: https://phys.org/news/2014-11-largest-factored-quantum-devic...
If you’re interested in quantum computing, spin is the most applicable place to start, as a qubit can be identically represented as a spin-1/2 particle.
I wouldn’t recommend Sakurai (which someone else mentioned) if you’re just starting. It’s what I used in grad school, and doable depending on your math background and motivation, but not the easiest intro.
Is it called post-quantum cryptography.
I’m not being Socratic, I just don’t know.
Real computation can.