13 ms·
The Era of Quantum Computing Is Here. Outlook: Cloudy
- adamnemecek 9y agoQubits are a bad idea. You want continuous variable quantum computing. https://en.m.wikipedia.org/wiki/Continuous-variable_quantum_information https://en.m.wikipedia.org/wiki/Continuous-variable_quantum_...
- Florin_Andrei 9y agoThose seem more similar to old school analog computers, in a sense.
- adamnemecek 9y agoThey very much are.
- krastanov 9y agoThe interesting thing is that a perfect analog classical computer is more powerful than the qubit quantum computer model (which is what people mean by quantum computing). But analog computers (whether classical or quantum) do not permit error correction, and as such are useless for anything but the smallest problem. You need bits and qubits in the real world.
- eindiran 9y agoThe wiki article says twice that a the motivation for studying continuous variable quantum computing is to understand "the ways in which quantum computers can be more capable or powerful than classical ones". But it never explains why you want to use continuous variable quantum computing over qubits. What are your arguments for why the correct path forward is not qubits?
- ianai 9y agoWhy do the real numbers solve more rational equations than the integers? They’re both infinite (though not equinumerous), but the integers can only come close to the reals.
- jjaredsimpson 9y agoBut now you have to demonstrate that your analogy holds.
- krastanov 9y agoAnd this line of reasoning completely fails when you start considering error correction. This is why we need bits and qubits. Aaronson's lecture notes go into the mathematical details if you are interested.
- IntronExon 9y agoWhat makes qubits a bad idea? What problems of qubits does continuous variable quantum computing solve? I’m not being Socratic, I just don’t know.
- ianai 9y agoMy guess is the quantum computer that Feynman theorized about was continuous. I’d bet it needs to be continuous to solve all the NP problems and so on.
- dangirsh 9y agoNo variant of quantum computing is expected to solve NP problems in polynomial time. That's just a common misconception.
- adamnemecek 9y agohttps://en.m.wikipedia.org/wiki/Real_computation https://en.m.wikipedia.org/wiki/Real_computation Real computation can.
- IntronExon 9y agoIn principle. Not in the actual universe we inhabit, with its Beckenstein Bound.
- adamnemecek 9y agoArbitrary precision (not infinite) is good enough for me.
- IntronExon 9y agoSort of like coming arbitrarily close to the speed of light, in that it will require energy on the same asymptotic scale you’re hoping to achieve precision in. Degenerate matter computers?
- krastanov 9y agoThis is pretty common misconception (that qubits are a bad idea). Qubits or qudits are necessary to achieve scalable error correction. I work at one of the research institutes that pushes the use of continuous variable systems (they are great). But we implement qubits on top of them (that is the whole point).
- gaze 9y agoThey’re equivalent. A continuum can be encoded into qubits and vis versa.
- adamnemecek 9y agoThey definitely aren’t.
- gaze 9y agoConsider an array of qubits forming a register. Now, a cavity resonator’s state can be expanded in a photon number basis. If you truncate the cavity resonator to 2^n photons, then map the 0 photon ket to the 0 state of the register, the 1 photon key to the 1 state of the register, all the way up to the 2^n photon state of the register to the 2^n photon state of the register. Now you’ve mapped the cavity state onto the register and they’re informationally equivalent
- adamnemecek 9y agosure, however analog computing has the advantage that you can solve optimization problems natively, in hardware. with qubits, you get a speedup but not O(1) solutions.
- gaze 9y agoAbsolutely not. The time complexity is exactly the same. A quantum computer can simulate quantum annealing with exactly the same asymptotic complexity as an “analog” physical system that takes advantage of quantum mechanics would.
- adamnemecek 9y agoI disagree but ok.
- Kequc 9y agoForgive me if I've missed it but I haven't seen any evidence that quantum computing has been used to solve even a very simple calculation. It seems that the purpose behind trying to build a quantum computer; is you really need to be out in front, not necessarily that it is possible. Are quantum computers just the fusion reactors of the computing world? Maybe one won't be built for 20 or 30 years, maybe longer.
- blattimwind 9y ago"The largest known number factored by Shor's algorithm on a quantum computer is 21."
- zitterbewegung 9y agoAt this point yes . We need ~70 years of research to get to something useful ( I asked my professor about this who I studied quantum computing this).
- jessriedel 9y agoThis is not a typical view among experts. Most numbers quoted are between 10 and 30 years for commercially useful devices.
- brain5ide 9y agoThose quotes have been around for the last 10 to 30 years, however. So 70 is a very sane number.
- booleandilemma 9y agoRelevant xkcd: https://xkcd.com/678/ https://xkcd.com/678/
- jessriedel 9y agoThis is simply not true. 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.
- currymj 9y agoMicrosoft's Q# is interesting. It's framed in a way that seems weirdly premature, but it is probably the nicest platform to learn about and play with quantum algorithms. Better than multiplying huge matrices in Octave, for sure.
- bdamm 9y agoThat’s outstanding. Have you solved anything with it?
- currymj 9y agoonly extremely basic stuff, nearly done with Deutsch-Josza now. 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.
- wRastel27 9y agoIt's definitely the most developer-friendly language that heavily borrows from their functional F# language. Microsoft has put a heavy bet into simulation so that they have a bit more of a runway before they need to produce a working quantum computer based on topological architecture. Interesting that they are targeting developers whereas most other languages are targeting scientists.
- cbHXBY1D 9y agoIt's written in F# so it makes sense it draws inspiration from it.
- codekilla 9y agoFor a great perspective read this: https://arxiv.org/abs/1801.00862 https://arxiv.org/abs/1801.00862 This is a write up of his keynote talk at Q2b this year.
- ggm 9y agoI asked some people a few years back if some equivalent to Moores law on the qbit size, and what it meant for cryptography applied. Their answer was that there wasn't good evidence of a direct linkage at the qbit density we had now, to achievable breaks in RSA, but that also the fundamental metric was probably wrong right now. Yes, how many qbits is interesting. But also how stable they are, how many states you can demonstrate, which specific solutions you target in open questions which QC can address.
- rowyourboat 9y agoThe article mentions this problem, and there seems to be a concept emerging that is called "volume": Basically, how complex the algorithm can be you can run on a quantum computer, taking into account the number of qubits, their error rate, the stability, ...
- blattimwind 9y agoI hope that we see some analysis done on this subject in the near future, because the rising uncertainty regarding current public-key tech is starting to get difficult for certain businesses.
- anfilt 9y agoThere is a Public crypto system based off error correcting codes that is quantumly secure. It's the McEliece cryptosystem, it's about as old as RSA. However, the key sizes are in 10's of thousands to 100's of thousands of bits. 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.
- dsacco 9y agoMcEliece has had significant cryptanalytic attention since the 70s, when it was first invented. In fact, it’s probably the most well studied post-quantum proposal, and it’s not really waiting on any further cryptanalysis. It’s currently considered secure (with binary Goppa codes) and has modes for both encryption and digital signatures via Neiderreiter, but it doesn’t support key exchange. 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.
- sundarurfriend 9y ago> Note that I’ve not said — as it often is said — that a quantum computer has an advantage because the availability of superpositions hugely increases the number of states it can encode, relative to classical bits. Nor have I said that entanglement permits many calculations to be carried out in parallel. 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_distances/ http://lesswrong.com/lw/kg/expecting_short_inferential_dista...
- Klathmon 9y agoI'm also glad they didn't fallback on the "easy" explanation. Funnily enough, an SMBC comic [0] is what made quantum computing "click" for me, and how it's not really easily mappable back to classical ideas. The comic was a joint effort with Scott Aaronson and SMBC creator Zach Weinersmith, and as far as I can tell is pretty close to a faithful explanation of the basics without diving into the technical details. [0] https://www.smbc-comics.com/comic/the-talk-3 https://www.smbc-comics.com/comic/the-talk-3
- sundarurfriend 9y agoThanks a lot for that link. That comic was a ton of fun (as one would expect from SMBC).
- connorelsea 9y agoIf this comic isn't diving into technical details then I must be an idiot
- Klathmon 9y agoI meant more that it's not trying to act like a whitepaper and "prove" the concepts it's explaining, which I think a lot of explanations of really complex topics end up spending way too much time on and lose the reader. 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).
- vtomole 9y agoThere are a lot of proposals for making logical qubits. One of the more favorable is a two dimensional surface code [0]. Current experiments suggest that it is possible to scale superconducting processors to around 100 physical qubits [1] of relatively high quality. It should be possible to perform significant error correction experiments on them. 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. [0]: https://en.wikipedia.org/wiki/Toric_code https://en.wikipedia.org/wiki/Toric_code [1]: https://www.nature.com/articles/s41534-016-0004-0 https://www.nature.com/articles/s41534-016-0004-0
- reikonomusha 9y agoRigetti Quantum Computing [0] is a YC startup that actually manufactures real quantum computers that are accessible through Forest. 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. [0] https://www.rigetti.com https://www.rigetti.com [1] “Lisp at the Frontier of Computation” https://youtu.be/f9vRcSAneiw https://youtu.be/f9vRcSAneiw [2] Rigetti talk at QIP 2017 https://youtu.be/IpoASc18P5Q https://youtu.be/IpoASc18P5Q [3] https://github.com/rigetticomputing/pyquil https://github.com/rigetticomputing/pyquil
- seiferteric 9y agoI am out of the loop, are there any "real" quantum computers yet? I was under the impression that no one was really making actual quantum computers yet, but some sort of annealing machine like d-wave. Are these IBM machines finally "real" quantum computers?
- obastani 9y agoD-Wave is not a "real" quantum computer in the sense that it is not asymptotically faster than a classical computer. Quantum computers with very few Quibits have existed for a while -- I believe the current record is 17 quibits [1]. I believe that to factor an n-bit integer, you need roughly n bits. So right now, we can factor 17 bit integers, which isn't very useful yet. However, I have read that for quantum simulations, it 30 quibit quantum computers might already be useful. [1] https://en.wikipedia.org/wiki/Timeline_of_quantum_computing https://en.wikipedia.org/wiki/Timeline_of_quantum_computing
- krastanov 9y agoIt is worse than that. To factor n bit number you need roughly n "logical" qubits, i.e. qubits that can store information almost indefinitely. The quantum computers that we have contain low quality "physical" qubits that lose their content after a few millisecond. You need to put an error correcting code on top of the physical qubits to encode the logical qubits. You can expect to need 100s or 1000s of physical qubits per logical qubit. I.e. to decode modern public key encryption you need a computer with millions of qubits. Today we have less than 50 in the best research hardware on the planet.
- gaze 9y agoOr a good cavity or two.
- marcosdumay 9y agoThis one I don't get. Isn't "a few milliseconds" more than enough time to gather a guess on integer factorization (and most of the useful problems)? Wouldn't it suffice to run your program again and again over the same short-lived qubits?
- YTGRK 9y agohttps://youtu.be/VIoEpU7GUoE https://youtu.be/VIoEpU7GUoE
- vadansky 9y agoThe discussion reignited my desire to learn quantum mechanics on the side. Usually the Geiffiths book is recommended, is this still the best intro to quantum mechanics?
- edna314 9y agoCertainly a matter of taste. I'd recommend "Modern Quantum Mechanics" from Sakurai.
- jeffwass 9y agoI used both Griffiths and Townsend’s books in undergrad QM classes, they complement each other nicely. It’s been awhile, but IIRC Griffiths starts off with a focus on continuous wave functions while Townsend starts off with spin and discrete states. 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.
- cortexio 9y agoStop believing in quantum computing please. It's all based on superposition which doesn't work in reality. It's a theoretical concept. In theory something can be a or b in superposition with another a or b. But in reality one will be a and the other b no matter whether you observe it or not. I'd like to see an explanation for the double slit experiment. Maybe then we can move on to more complex things. It's also possible that the double slit experiment isn't even based on observation, but rather a logical mistake in our end. Who knows...
- tomerbd 9y agowhat will happen to RSA encryption once they are here?
- pjmlp 9y agoGone, but there are quantum safe algorithms, we just need to migrate to them as industry. Is it called post-quantum cryptography. https://en.wikipedia.org/wiki/Post-quantum_cryptography https://en.wikipedia.org/wiki/Post-quantum_cryptography
- workthrowaway27 9y agoI wonder why we should expect practical quantum computing to be here any sooner than practical nuclear fusion?
- Robotbeat 9y agoThe article, as carefully as it seems to be written compared to many pop sci articles on the topic, contains many errors or mischaracterizations. For instance: 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.