A Tiny Startup Racing Google to Build a Quantum Computing Chip(technologyreview.com)
technologyreview.com
A Tiny Startup Racing Google to Build a Quantum Computing Chip
https://www.technologyreview.com/s/600711/the-tiny-startup-racing-google-to-build-a-quantum-computing-chip/
5 comments
Funny how Google's name is essentially dropped into the article (and the lead) in a purely clickbait style. Guess not even MIT is immune to it.
I don't know if you've ever read an MIT press release, but they overhype and misrepresent the science coming out of their institution like it's going out of style. It's endemic in nearly all universities, especially the big name ones. This should not be a surprise.
Hmmm.
There are like 5 superconductor guys and 3 ion trapping guys, so I guess they're going for superconductor qubits. Unless they're doing way better than the superconductor groups in academia, I wouldn't hold your breath, it's still pretty far from a workable technology.
There are like 5 superconductor guys and 3 ion trapping guys, so I guess they're going for superconductor qubits. Unless they're doing way better than the superconductor groups in academia, I wouldn't hold your breath, it's still pretty far from a workable technology.
Also pretty clear they are going for superconductor qubits given that they say they are using dilution fridges, the founder worked at IBM, and did his PhD on superconductor qubits...
It's definitely, definitely superconducting qubits.
Martinis and Tureci are doing pretty well, what's your beef?
We're living in an interesting time. The first group to get a working qbit based computer will be able to break all current encryption. We will very rapidly have to switch to quantum encryption to protect ourselves.
You can be damn sure that the NSA and the other three letter agencies are working hard on this problem, and definitely would not share if they get there first (if they haven't already).
You can be damn sure that the NSA and the other three letter agencies are working hard on this problem, and definitely would not share if they get there first (if they haven't already).
You don't need quantum cryptography to defend against attacks that employ quantum computers.
There was an interesting talk on classical encryption algorithms that resist quantum attacks by djb and Tanja Lange at 32c3 last year, see [1,2,3].
TL;DR:
- Shor's algorithm kills factorization-based algorithms like RSA, DSA and including elliptic-curves-based DSA,
- Grover's algorithm allows faster (O(sqrt(N) instead of O(n)) brute-force searches, which means for the same level of security, one needs to double AES key size,
- there exist classical encryption algorithms that have so far resisted quantum-based attacks, e.g. hash-based signatures, Goppa code-based asymmetric crypto,
[1] https://www.youtube.com/watch?v=6XeBvdm8vao
[2] https://media.ccc.de/v/32c3-7210-pqchacks#video (in German)
[3] https://www.reddit.com/r/privacy/comments/3yppbz/post_quantu...
EDIT: formatting
There was an interesting talk on classical encryption algorithms that resist quantum attacks by djb and Tanja Lange at 32c3 last year, see [1,2,3].
TL;DR:
- Shor's algorithm kills factorization-based algorithms like RSA, DSA and including elliptic-curves-based DSA,
- Grover's algorithm allows faster (O(sqrt(N) instead of O(n)) brute-force searches, which means for the same level of security, one needs to double AES key size,
- there exist classical encryption algorithms that have so far resisted quantum-based attacks, e.g. hash-based signatures, Goppa code-based asymmetric crypto,
[1] https://www.youtube.com/watch?v=6XeBvdm8vao
[2] https://media.ccc.de/v/32c3-7210-pqchacks#video (in German)
[3] https://www.reddit.com/r/privacy/comments/3yppbz/post_quantu...
EDIT: formatting
There's been some good work in Merkle Signatures in recent times. I posted a bunch on Schneier's blog here:
https://www.schneier.com/blog/archives/2015/03/friday_squid_...
https://www.schneier.com/blog/archives/2015/03/friday_squid_...
My understanding is that it is not enough to just be a "qbit based computer" to be able to solve QBP (i.e. perform shors algorithm to break RSA).
These computers are quantum adiabatic computers which are indeed quantum in that they use qbits, but it is not clear that they can perform some operations required for QBP problems. See scott aaronson's blog for more info [1].
1. http://www.scottaaronson.com/blog/?p=1400
These computers are quantum adiabatic computers which are indeed quantum in that they use qbits, but it is not clear that they can perform some operations required for QBP problems. See scott aaronson's blog for more info [1].
1. http://www.scottaaronson.com/blog/?p=1400
In Scott Aaronson's book Quantum Computing Since Democritus, he off-handedly mentions the need for quantum-hard crypto and that perhaps something based on Wolfram's cellular automata would do the trick. Wolfram says he used one of his own cellular automata rules as the PRNG in Mathematica. Which makes me wonder, why don't we already use something like this in modern crypto? And, how exactly would we implement this if we wanted to do so?
I'm not nearly well versed enough to speak intelligently on the subject, but my understanding is that only quantum computers can do a "perfect" key exchange, because the detection of interference by a third party can only be detected by a quantum computer.
Kind of, quantum key exchange is based on the uncertainty principle. By encoding the key exchange in quantum properties of particles, any mitm observer will change those properties, thus breaking the exchange. You don't need a quantum computer to do QKE, just the right kind of detector. There's already a bunch of people that do this without quantum computers.
> The first group to get a working qbit based computer will be able to break all current encryption.
All you have to do is increase the key-size faster than quantum can break it. Also there are many new algorithms being studied that quantum doesn't work on.
https://en.wikipedia.org/wiki/Post-quantum_cryptography
All you have to do is increase the key-size faster than quantum can break it. Also there are many new algorithms being studied that quantum doesn't work on.
https://en.wikipedia.org/wiki/Post-quantum_cryptography
Good luck to them, and here's hoping that they can make some progress.
In case this leads to the usual "what's so hard about quantum computing that these big companies are struggling with it, and how can a small company possibly hope to beat Google?" let me try to explain.
Quantum computers seem to do some stuff more efficiently than any classical computer can. Exact proofs are hard to come by. (The classes are BQP and BPP, with a straightforward proof that BPP is in BQP. We now have a bunch of oracles Q Such that BQP^Q /= BPP^Q, but that's not necessarily a proof because of course we now have oracles A and B such that P^A = NP^A but P^B /= NP^B. So we have "some evidence" that quantum computers can do things faster than classical computers, but it's not hard proof yet.) Those parenthesized concerns aside, quantum computers seem to be more efficient than classical ones at some tasks.
We call by the name "interference" this property which crucially dictates how quantum computers do stuff differently. Essentially, instead of using probabilities with real numbers between 0 and 1, quantum mechanics uses scaled rotation matrices, which we call "amplitudes" and often represent as complex numbers. We bound the scale factor between 0 and 1 and interpret its square as a probability, which yields the same result as multiplying the complex number by its complex conjugate, or multiplying the matrix by its transpose: these are all mathematically equivalent. In this framework, if the qubit |0> produces an amplitude-pattern f(z) on some screen (hence you'll see |f(z)|^2 as the pattern) and |1> evolves to g(z), then the "quantum superposition" a|0> + b |1> (where a, b are complex numbers) evolves to produce the pattern |a f(z) + b g(z)|^2, which might show some sort of "wavy interference pattern" wherever the original patterns |f(z)|^2 and |g(z)|^2 overlap.
These interference effects can also be seen over multi-bit quantum states like the system a|00> + b|11>. In such a circumstance we call those two parts "entangled", and we can prove that there is no precise quantum description which "separates" the two quantum-bits. However physicists have proven a crucial theorem in quantum mechanics: when you look at one of those entangled-parts in isolation, it behaves according to classical probability laws. This is derivable purely from the mathematics of these complex amplitudes and we usually call it "tracing out" the rest of the system, if you want a convenient jargon term.
What entangles a system with a quantum-bit? Anything which interacts differently based on whether the quantum-bit is 0 or 1. The intersection of these two concerns -- the universality of entanglement and the classicalness that entanglement creates -- is the thing which makes quantum computing complicated. The very interference effects which make quantum computing powerful disappear the moment that "anything else" entangles with our precious quantum bits: and this includes any part of the external world (so the quantum state needs to be well isolated from anything that is not its logic), but also the computer itself (the complicated "quantum gates" that we need to implement to guide the state in whatever direction it's going). If any of those things entangle passively with the quantum state, the parts that we can measure stop showing interference effects and start acting like classical probabilistic mixtures.
This problem in general is called "decoherence" and it is the hard problem in the "DiVincenzo Criteria", which are the 5 joint concerns of quantum computation. So there are basically 4 other things that you basically are not allowed to compromise to kill decoherence: (a) a qubit-centric system of states |00...0>, |00...1>, ... |11...1>, which (b) can be initialized to a known starting state |00...0>, and then (c) its qubits can be manipulated by a set of universal quantum gates, which then (d) are measured to be either 0 or 1.
So that's where somebody who has a really bright insight about solving this "decoherence" problem could really leap light-years ahead of a bunch of highly-paid engineers and scientists who lack the crucial insight.
In case this leads to the usual "what's so hard about quantum computing that these big companies are struggling with it, and how can a small company possibly hope to beat Google?" let me try to explain.
Quantum computers seem to do some stuff more efficiently than any classical computer can. Exact proofs are hard to come by. (The classes are BQP and BPP, with a straightforward proof that BPP is in BQP. We now have a bunch of oracles Q Such that BQP^Q /= BPP^Q, but that's not necessarily a proof because of course we now have oracles A and B such that P^A = NP^A but P^B /= NP^B. So we have "some evidence" that quantum computers can do things faster than classical computers, but it's not hard proof yet.) Those parenthesized concerns aside, quantum computers seem to be more efficient than classical ones at some tasks.
We call by the name "interference" this property which crucially dictates how quantum computers do stuff differently. Essentially, instead of using probabilities with real numbers between 0 and 1, quantum mechanics uses scaled rotation matrices, which we call "amplitudes" and often represent as complex numbers. We bound the scale factor between 0 and 1 and interpret its square as a probability, which yields the same result as multiplying the complex number by its complex conjugate, or multiplying the matrix by its transpose: these are all mathematically equivalent. In this framework, if the qubit |0> produces an amplitude-pattern f(z) on some screen (hence you'll see |f(z)|^2 as the pattern) and |1> evolves to g(z), then the "quantum superposition" a|0> + b |1> (where a, b are complex numbers) evolves to produce the pattern |a f(z) + b g(z)|^2, which might show some sort of "wavy interference pattern" wherever the original patterns |f(z)|^2 and |g(z)|^2 overlap.
These interference effects can also be seen over multi-bit quantum states like the system a|00> + b|11>. In such a circumstance we call those two parts "entangled", and we can prove that there is no precise quantum description which "separates" the two quantum-bits. However physicists have proven a crucial theorem in quantum mechanics: when you look at one of those entangled-parts in isolation, it behaves according to classical probability laws. This is derivable purely from the mathematics of these complex amplitudes and we usually call it "tracing out" the rest of the system, if you want a convenient jargon term.
What entangles a system with a quantum-bit? Anything which interacts differently based on whether the quantum-bit is 0 or 1. The intersection of these two concerns -- the universality of entanglement and the classicalness that entanglement creates -- is the thing which makes quantum computing complicated. The very interference effects which make quantum computing powerful disappear the moment that "anything else" entangles with our precious quantum bits: and this includes any part of the external world (so the quantum state needs to be well isolated from anything that is not its logic), but also the computer itself (the complicated "quantum gates" that we need to implement to guide the state in whatever direction it's going). If any of those things entangle passively with the quantum state, the parts that we can measure stop showing interference effects and start acting like classical probabilistic mixtures.
This problem in general is called "decoherence" and it is the hard problem in the "DiVincenzo Criteria", which are the 5 joint concerns of quantum computation. So there are basically 4 other things that you basically are not allowed to compromise to kill decoherence: (a) a qubit-centric system of states |00...0>, |00...1>, ... |11...1>, which (b) can be initialized to a known starting state |00...0>, and then (c) its qubits can be manipulated by a set of universal quantum gates, which then (d) are measured to be either 0 or 1.
So that's where somebody who has a really bright insight about solving this "decoherence" problem could really leap light-years ahead of a bunch of highly-paid engineers and scientists who lack the crucial insight.
Passive error correction has made blindingly good progress in the last few years.
cat codes, man.
Can you contact me at my HN handle at gmail.com? I might have some technical questions for you - I'm looking to start a thesis project on many body localization as it applies to these sort of systems with nonlinear drive terms.
Looking forward to Prof. Scott Aaronson [0]'s response to this.
[0] http://www.scottaaronson.com/
[0] http://www.scottaaronson.com/