9 ms·
The Machine of Tomorrow Today: Quantum Computing on the Verge
- davedx 9y agoIt's going to be fun working in cryptography soon.
- dsacco 9y agoIt already is! There are a huge number of research opportunities.
- deleted 9y ago[deleted]
- MichaelBurge 9y agoBesides scientists, I don't really see quantum computers as being useful computationally. There's breaking cryptography, but then you're spending billions to inconvenience people into moving to a different quantum-resistant algorithm. What about creating cryptography? Wikipedia has a few interesting applications: https://en.wikipedia.org/wiki/Quantum_cryptography https://en.wikipedia.org/wiki/Quantum_cryptography I'm not a cryptographer - are security people excited about building all sorts of weird quantum protocols? > “Then you let the computer check all possible solutions essentially—or a very large combination of them—and come back with an answer,” he says. In a quantum computer, there’s no mathematician cracking the problem, he says. “The laws of physics crack the problem for you.” That sounds more like an NTM than a quantum computer. An NTM would turn its owner into a God. > Superposition is the mind-bending observation that a particle can be in two states at the same time. Bring out your ruler to get a measurement, however, and the particle will collapse into one state or the other. And you won’t know which until you try, except in terms of probabilities. It's not probabilities because people think of those as real numbers. The coefficients are complex numbers. There's a probability monad, for example, but no quantum monad: http://twistedoakstudios.com/blog/Post5485_what-isnt-a-monad http://twistedoakstudios.com/blog/Post5485_what-isnt-a-monad The article sort of mentions it later on when they quote Scott Aaronson, but I suspect the author didn't understand and mentally reverted back to a probability model.
- hannob 9y ago> I'm not a cryptographer - are security people excited about building all sorts of weird quantum protocols? No. In reality so-called quantum cryptography is completely impractical. Imagine an Internet where you can't send messages to people more than a few hundred kilometers away, with no wifi and no mobile Internet and which only works if you have pre-shared keys. That's the Quantum Internet (which apparently the EU just decided to fund with billions).
- doktrin 9y ago>> > I'm not a cryptographer - are security people excited about building all sorts of weird quantum protocols? > No. In reality so-called quantum cryptography is completely impractical What about building quantum safe protocols? Is that as a field any more interesting and/or viable?
- hannob 9y ago> What about building quantum safe protocols? Is that as a field any more interesting and/or viable? Yes. Plenty of stuff happening in that field. The challenge is: Right now we can choose between probably safe, but impractical (mcbits, sphincs) and practical, but with big questionmarks about how safe they are (newhope, sidh). The problem is: We really only trust crypto algos if they have been tested and researched over a long time, but lots of these things are pretty new.
- CiPHPerCoder 9y agoThat's called post-quantum cryptography, not quantum cryptography.
- doktrin 9y ago>> What about building quantum safe protocols? > That's called post-quantum cryptography, not quantum cryptography. As I understand it, "quantum safe" and "post-quantum" describe the same thing. I never used the term 'quantum cryptography'
- kwelstr 9y agoI wonder if and when we have working quantum computers bitcoin and crypto will be able to adapt or die. I mean, breaking secret keys with quantum should be easy.
- danenania 9y agoExisting crypto would be broken, but quantum computation also seems provide much stronger encryption possibilities by leveraging entanglement states. [1] 1: https://en.m.wikipedia.org/wiki/Quantum_cryptography https://en.m.wikipedia.org/wiki/Quantum_cryptography
- dsacco 9y agoNot all existing crypto would be broken. Symmetric encryption algorithms like AES will be fine. Asymmetric encryption (public-key) algorithms like RSA/DSA will be in trouble due to Shor's algorithm, but other public-key systems will be fine. Hash functions like SHA-2 and SHA-3 will be mostly fine, because Grover's algorithm is at best sub-exponential, not quadratic. Also, quantum cryptography mostly provides superior key establishment/management capabilities, not superior confidentiality guarantees. It's a misnomer to state that we can achieve "stronger encryption" by "leveraging entanglement states"; most of quantum computing is useful for cryptanalytic attacks right now, not cryptographic construction.
- danenania 9y agoThanks, that's very enlightening!
- zamalek 9y agoMerkle–Damgård algorithms are thought to be safe. I'm not sure about Keccak.
- dsacco 9y agoKeccak (SHA-3) is currently thought to be safe. The current state of the art would be Brassard-Hoyer-Tapp[1], but SHA3-512 should be secure against that. It's basically a birthday attack that generates a giant table, then uses Grover's algorithm to find a collision. _______ 1. https://link.springer.com/chapter/10.1007%2FBFb0054319 https://link.springer.com/chapter/10.1007%2FBFb0054319
- Asdfbla 9y agoSince questions about crypto came up, here's a summary paper by Daniel Bernstein about it: https://eprint.iacr.org/2017/314.pdf https://eprint.iacr.org/2017/314.pdf Symmetric cryptography would be safe even with quantum computers (they just half the effective bit length of the cypher with Grover's algorithm, which can be compensated for by increasing the key length). Classical asymmetric cryptography would be in danger, but there are alternative systems for which no quantum based attacks are known. They can be a bit unwieldy to use and have much larger key sizes than what we currently use - but methods that are hopefully quantum-proof may exist. The Lamport signature scheme is probably one of the methods that is the easiest to understand. Not all hope is lost for cryptography even with quantum computers.
- dsacco 9y agoThe forecast for hash functions is also optimistic (same deal as symmetric encryption with respect to Grover's algorithm). Not all asymmetric key cryptography is in danger either. Lattice-reduction and McEliece encryption schemes don't have a known weakness to post-quantum computing.
- reikonomusha 9y agoAs someone who works in the field of quantum computation, it's actually a little unpleasant that crypto always comes up. Crypto is interesting and quantum computers do have a part in it, but it's one of the least interesting things to talk about when it comes to what quantum computers can do. It's like at the advent of the regular computer, and the application everyone talks about is how it will be able to do accounting. It's right, but there are so many other interesting things it can do. To offer some fodder for further discussion, how about molecular and atomic simulation? Wouldn't it be nice if we could just simulate the behavior of a molecule to predict what useful properties it has? One could imagine just exhaustively searching for molecules of interest on a quantum computer. Or how about using a quantum computer to bootstrap itself? Using a QC to build a better QC is in the realm of its utility. Or how about solving some of these nasty computer science problems that crop their heads up everywhere, like graph coloring (or any of its equivalent incarnations)? Factoring integers and searching boxes are really interesting developments in the theory of quantum computation, but the above stuff, to me, sounds a lot cooler.
- mrhektor 9y agoDoes anybody know of any good links / blog posts that explain the actual inner workings of a quantum computer in more detail?
- dsacco 9y agoSure. Here are a few resources; they vary in technical complexity and depth of coverage, but they're all rigorous: Scott Aaronson has a good introductory article in Scientific American[1], and he also wrote a short, accessible article aimed at high school students in 2002[2]. Then there's Berkeley's CS 191 Qubits, Quantum Mechanics and Computers syllabus and lectures[3]. Tel Aviv University has lecture notes for the 1997 Quantum Information Processing course online[4]. These are old, but the information is still fundamentally accurate if what you're looking for is a breadth-wise introduction to the topic. There's the paper, From Cbits to Qbits: Teaching Computer Scientists Quantum Mechanics on arXiv[5]. I assume you have a computer science background; if that's the case, you might want to start with for light reading on the meta between classical and quantum computing, then dive into one of the lecture notes series. The first two resources are much more digestible; if you're looking for something to read in 10 minutes or so and come away with a basic understanding of the field, those are what you want to read. _________ 1. http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf http://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Com... 2. http://www.scottaaronson.com/writings/highschool.html http://www.scottaaronson.com/writings/highschool.html 3. http://www-inst.eecs.berkeley.edu/~cs191/sp05/ http://www-inst.eecs.berkeley.edu/~cs191/sp05/ 4. http://www.tau.ac.il/~tsirel/Courses/QuantInf/syllabus.html http://www.tau.ac.il/~tsirel/Courses/QuantInf/syllabus.html 5. https://arxiv.org/abs/quant-ph/0207118 https://arxiv.org/abs/quant-ph/0207118
- mrhektor 9y agoThanks, they're on my reading list!
- jessriedel 9y agoNote that all of these links appear to concentrate on abstract computation principles analogous to learning about computation in a CS course. I don't think they actually describe the physical inner workings of a quantum computer.
- nerflad 9y agoEvery article I read focusses on how quantum computing differ from classical at a high level. I know these are probably asinine questions, but how are these computers actually used? How are these experiments instructed to the machine? Do these machines have I/O? Does the state of the qubits have to be measured with separate equipment?
- jessriedel 9y agoThese "computers" are just experiments in a lab right now. The qubits are prepared and read out by highly specialized equipment that differs depending on the substrate being pursued (e.g., lasers for trapped ions, cryogenic amplifiers for SQUIDs, etc.). To make an analogy with classical computation, imagine wiring the very first transistors together by hand and computing 2+2 using a voltage supply and an oscilloscope.
- nabla9 9y agoQuantum computer as a physical device means quantum circuit. Each quantum computer is special purpose circuit implementing single algorithm. Because quantum computation works trough destructive interference, there is no interaction during execution. You insert the input, run it trough circuit and extract the result as classical output at some point. The whole setup science experiment looking gadget sitting in the lab (with the exception of Dwave). Universal quantum computer (aka Quantum Turing Machine) is concept used in computational complexity theory. I'm not aware of any suggested physical implementation of universal programmable quantum computer. I don't even know if it makes any sense.
- reikonomusha 9y agoUniversal quantum computers do indeed exist. It's true that some quantum devices are special purpose (e.g., D-Wave's annealers), but most groups doing quantum computation are doing universal gate-based machines (e.g., Rigetti, Google, IBM, etc.). They're just being made at small scales right now (2-50 qubits).
- deleted 9y ago
- basicplus2 9y agoI'll believe in a quantum computer when I see one.
- virgil_disgr4ce 9y ago"Quantum Computing Might Be Here Sooner Than You Think" Haven't these stories had this same headline for at least 10 years now?
- dekhn 9y agoyep, just like fusion. I do think the money is on Martinis actually showing a basic working 49-bit QC in the next year, though.
- reikonomusha 9y agoExponential progress is still exponential progress. The quality of quantum devices has increased exponentially in a variety of ways over the past couple of decades.
- goatlover 9y agoIs that similar to the exponential progress in flying cars since the 50s?
- deleted 9y ago[deleted]
- gregfjohnson 9y agoIs it possible that protecting superposition and entanglement will be a fundamental problem for scaling quantum computing? I could imagine that beyond some point, each time you add an extra qubit the cost of shielding the computation goes up by a multiplicative factor. Say the observable universe has something like 10^100 subatomic particles total. I believe that by current estimates, this is an upper bound. A quantum computer with 350 qubits would have 2^350 states, or more states than the total number of subatomic particles in the universe. A single "NOT" operation on one of those qubits would, in constant time, change half of those states. I.e., the quantum computer would do way more work than there are particles in the observable universe. For every single one of its operations. I just don't see how the universe will let nerds on some tiny little out-of-the-way planet get away with that. QC demonstrably works for small numbers of qubits. I just wonder if it will ever scale to the point that large problems can be tackled with QC in a cost-effective manner.
- anoonmoose 9y ago10^50 atoms on Earth, 2^1024 states in a purely combinational circuit, I wouldn't be shocked if someone once said something similar about scaling silicon, with some different speed constraint.
- bykovich2 9y agoNumber of states in a superposition and number of particles in the universe aren't really related measurements at all (except in the most trivial way) -- at least so far as I can see.