5 ms·
Note that they have a quantum computer that can solve a very specific type of problem. (But it solves them exponentially faster than a classical computer). They
by gus_massa 7y ago
Note that they have a quantum computer that can solve a very specific type of problem. (But it solves them exponentially faster than a classical computer). They don't have a general purpose quantum computer, in particular, they can't run Shor's algorithm to factorize numbers and break a big part of encryption methods.
For a more detailed and better explanation than mine, you can read post of Scott Aaronson https://www.scottaaronson.com/blog/?p=4317 https://www.scottaaronson.com/blog/?p=4317 (HN discussion: https://news.ycombinator.com/item?id=21053405 https://news.ycombinator.com/item?id=21053405 (595 points, 5 days ago, 207 comments))
- balfirevic 7y ago> They don't have a general purpose quantum computer, in particular, they can't run Shor's algorithm to factorize numbers and break a big part of encryption methods. What limitations does it have, other than not having enough qubits to run Shor's algorithm (Scott Aaronson mentions it would require thousands of logical qubits, translating to possibly millions of physical qubits due to error-correction requirements)? Scott's FAQ says: "The key difference with Google’s effort is that they have a fully programmable device—one that you can program with an arbitrary sequence of nearest-neighbor 2-qubit gates, just by sending the appropriate signals from your classical computer." Unfortunately, I don't know what "arbitrary sequence of nearest-neighbor 2-qubit gates" means and what kinds of algorithms are out of reach for that method.
- krastanov 7y ago> arbitrary sequence of nearest-neighbor 2-qubit gates The classical equivalent is (very handwavily) a processor that can perform all the ops from a reasonable small ISA, but each op has 1% chance of failing silently. Hence, any quantum algorithm can be put on this device in principle, but you are limited to stuff that uses only 50 qubits and does not mind the 1% error. There are not really any useful things you can do in the presence of (accumulating) 1% errors, beside proof of concept contrived problems.
- BurningFrog 7y agoISA = Instruction Set Architecture https://en.wikipedia.org/wiki/Instruction_set_architecture https://en.wikipedia.org/wiki/Instruction_set_architecture
- eternalban 7y ago> What limitations does it have, other than not having enough qubits .. Would appreciate informed commentary on the scaling characteristic of the current approaches. It seems reasonable to question whether that the scaling challenge itself will prove to be as formidable as solving certain problems. Is it?
- octosphere 7y ago> in particular, they can't run Shor's algorithm to factorize numbers and break a big part of encryption methods Given a sufficient time horizon, large swathes of crypto will be broken by such a computer and has many people worried. NIST is working on algorithms resistant to quantum attacks, but we're still far off.
- Yajirobe 7y ago> NIST is working on algorithms resistant to quantum attacks, but we're still far off. These have existed for years already
- octosphere 7y agoYes but isn't there a competition to find an algo that can be widely deployed and not subject to weird requirements? A sort of 'goldilocks' algo. For example, I can't recall the name of the algo, but one such candidate for a post-quantum algo required keysizes to be 1TB in size. Another had large computation requirements and so thus couldn't do on-the-fly crypto (which is needed to do LUKS style encryption of disks for example). (Sorry for my lack of sources but it was a Youtube video of some talk about post-quantum crypto algos I randomly stumbled upon and forgot to bookmark)
- EGreg 7y agoExcuse me if I’m being ignorant but isn’t a quantum computer unable to reverse hashes? Are they going to make a preimage attack or a collision attack on SHA512 for example, by trying all combinations at once? If hashes are safe, then why not simply base our signatures and other stuff on them? The only thing that may be missing is actual encryption / decryption, but that can be done by XORing with “one-time” pads built from peeling onion layers from hashes.
- speakeron 7y agoA quantum computer can find hash collisions in the square root of the time a classical computer can using Grover's algorithm. (So a 256-bit hash becomes as difficult as a 128-bit hash to reverse). Symmetric encryption (e.g. AES) is the same, so encryption itself doesn't have any problems with quantum computing (if you consider 128-bit AES to be safe in general). Quantum computing affects the distribution of symmetric keys using public key encryption (and so affects a large amount of encryption as used in people's daily lives) which is vulnerable to quantum computers with sufficient bits.
- baybal2 7y ago> Note that they have a quantum computer that can solve a very specific type of problems. Yes, it's an adiabatic quantum computer, not different from D-Wave's device. Calling it a quantum computer is like bunching an electromechanical differential analysers with modern CPUs because both use electricity.
- evanb 7y agoIt's not an adiabatic machine. It's a gate-type machine, with registers that experience programmable interactions with its neighbors. That's very much more like a classical computer than an adiabatic machine.
- baybal2 7y agoTell me what is non adiabatic about it?
- krastanov 7y agoIn this context "adiabatic" usually refers to "slow continuous transition" (even if this is not the literal meaning of the word). This device uses the circuit model (discreet gates), not the adiabatic model (continuous transition between hamiltonians) of quantum computing. Your initial comment also had an imprecision that is pretty common: 1. Adiabatic quantum computers and circuit model quantum computers are equivalent models. 2. Dwave never constructed an adiabatic quantum computer, rather something they called a quantum annealer. These are interesting devices inspired by the model of adiabatic computers, but we do not have a reason to think they are better than classical computers.
- statusquoantefa 7y ago> (But it solves them exponentially faster than a classical computer) do you mean literally exponentially? or do you mean "a lot" faster?
- smountjoy 7y agoThe difference in running time grows exponentially with the size of the input. I'd say that's "literally" exponential.
- cgearhart 7y agoLiterally exponentially. But keep in mind that QC does not mean you can solve _any_ problem exponentially faster than a binary computer. If something is NP-Complete (or any of the less familiar “hard problem” classes) then it’s still gonna be hard for the quantum computer. So you’ll get an exponential speed up for some specific problems like quantum circuit sampling, but it can’t help you solve the Traveling Salesman Problem any faster unless we find a new algorithm—and even then that would imply P=NP. There’s still lots that QC could bring to the table even if it only works for some problems, but it’s not expected to completely replace classical computers—more like augment them with some new super powers.
- primaryobjects 7y agoThe Traveling Salesman Problem is indeed a potential application of quantum computing. Grover’s Search could theoretically find a solution in quadratic time (sqrt(n!) versus n!). On a physical quantum computer, this would have profound impact to many different real-world applications.
- teraflop 7y agoGrover's algorithm provides a quadratic speedup, but sqrt(n!) is not quadratic time; it's super-exponential.
- AlexCoventry 7y ago> For a more detailed and better explanation You can also read the actual paper: https://drive.google.com/file/u/1/d/19lv8p1fB47z1pEZVlfDXhop082Lc-kdD/view https://drive.google.com/file/u/1/d/19lv8p1fB47z1pEZVlfDXhop...
- erichocean 7y agoYes, it takes a classical computer more time to simulate a quantum computer than just running that quantum computer and checking the output. But did anyone think this wasn't going to be the case? Quantum circuit solving is just one example of this phenomenon; physically-based rendering is another: it's much faster to stick a camera in a room and measure the resulting image than it is to simulate light transport of the identical scene in the computer using an unbiased rendering algorithm. I'm sure there are other examples: any physical phenomenon that is "NP-like" will have this property where setting up the (physical) system and measuring the end result after it has "settled" is exponentially faster than simulating the entire system in a classical computer and then measuring the result.
- hcs 7y agoI think Aaronson addresses your objections in Q12, including claiming that there are some who didn't think even this would be possible (see also Q14). If you built a programmable room for creating a large variety of material and lighting setups under computer control, that might be comparable?