Quantum supremacy: the gloves are off | Hacker News Reader

Quantum supremacy: the gloves are off

scottaaronson.com

275 pointsfurcyd56 comments

Two key points:

> OK, so let’s carefully spell out what the IBM paper says. They argue that, by commandeering the full attention of Summit at Oak Ridge National Lab, the most powerful supercomputer that currently exists on Earth—one that fills the area of two basketball courts, and that (crucially) has 250 petabytes of hard disk space—one could just barely store the entire quantum state vector of Google’s 53-qubit Sycamore chip in hard disk. And once one had done that, one could simulate the chip in ~2.5 days, more-or-less just by updating the entire state vector by brute force, rather than the 10,000 years that Google had estimated on the basis of my and Lijie Chen’s “Schrödinger-Feynman algorithm” (which can get by with less memory).

> But does IBM’s analysis mean that “quantum supremacy” hasn’t been achieved? No, it doesn’t—at least, not under any definition of “quantum supremacy” that I’ve ever used.

Process arguments are rarely convincing and particularly not when the process is so technically complex.

Regardless of whether the Martinis team actually demonstrated quantum supremacy, their achievement is undoubtedly worth the praise it received. I built and operated a superconducting two-qubit processor for my PhD thesis in 2010, so I have a good understanding of the challenges invovled in operating and tuning qubits. For me, seeing the 53 qubit chip, its wiring setup and the control electronics is just breathtaking.

I think John's team neatly demonstrated that they are far ahead of the competition (e.g. Rigetti, IBM) in terms of maturity and qubit control, and if that's any indication of future success I would strongly bet on their team for building the first actually working quantum computer.

What is a "first actually working quantum computer" if not this Sycamore device that Google used to demonstrate quantum supremacy?

Maybe something that solves a natural problem instead of an artificial one.

One with fault-tolerance.

I reckon one that has quantum error correction on qubits which present Boolean values. I.e. one which could also run a classical program. That is the quantum computer which is actually a quantum Turing machine and which can do speedups of e.g. factorization. Unfortunately, it is hypothesized that such a quantum Turing machine will require about ~1000 qubits of this machine per qubit with error correction, maybe more.

For what it's worth, the FAQ on his blog dances around this topic:

"Running Shor’s algorithm to break the RSA cryptosystem would require several thousand logical qubits. With known error-correction methods, that could easily translate into millions of physical qubits, and those probably of a higher quality than any that exist today."

"How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits"

https://arxiv.org/abs/1905.09749

You could of course argue that it's already a quantum computer that they've built. It's not a general purpose quantum computer though, as it doesn't allow you to run arbitrary gate sequences on it due to limited coherence time and limited inter-qubit connectivity. So while you surely can do some quantum computations on it you can't yet run arbitrary quantum programs.

In terms of limited connectivity: mesh connectivity is theoretically sufficient. Putting all qubits in superposition in a preparation phase then allows you to do any arbitrary quantum computation by a sequence of measurements and one-qubit operations. You would be doing one-way measurement quantum computing, and not quantum circuits, but it's just as universal.

I'd love to see one that can compute energy levels for molecules that are larger than we can currently simulate on supercomputers. quantum chemistry simulations typically scale O(n7) where n = # of basis functions (usually larger than the number of atoms in the molecule).

I agree with you, but with a couple of corrections. The cheaper algorithm called Density Functional Theory is probably the most popular kind of quantum calculation on molecules, and scales as ~N^2.5 in practice. On the other hand, the number of basis functions is a more than the number of valence electrons in the molecule (if the calculation is at all sane), much larger than the number of atoms. So the exponent is often smaller than you said, but the N is also much bigger. So in the end you're absolutely right about the need for quantum computing for molecules.

Could you recommend a few books that someone with no particular knowledge on the subject could read to get a grasp on what's going on?

Scott Aaronson's book, Quantum Computing since Democritus, seemed remarkably easy to understand when I read it.

https://uwaterloo.ca/institute-for-quantum-computing/sites/c... Quantum Cryptography School for Young Students

Michael Nielsen has a nice series of blog articles on the subject:

http://michaelnielsen.org/

(look for "The Quantum World")

It looks so bizarre, not the computer as we know it: https://www.flickr.com/photos/ibm_research_zurich/4078696912...

Reminds me of the first transistor.

https://upload.wikimedia.org/wikipedia/commons/b/bf/Replica-...

It's a science experiment and unfinished proof of concept. Looks mad-sciencey.

These pictures are always really fun, but they're not really "the computer" -- most of what you see is the cooling system.

Hell, even the sight of complex mechanical computers like the Babbage difference engine will make me tremble.

https://upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Ba...

See it in action on YouTube.

I feel like I get a similar feeling when I see really alien-looking wind turbines.

Most of that is the refrigeration system needed to keep the device cold enough, see https://en.wikipedia.org/wiki/Dilution_refrigerator

As always, thank god for Scott Aaronson's blog! There is a lot of misinformation sown in popular science. Shtetl Optimized is just about the only science-related source that is simultaneously correct, accessible, timely, and widely read. That's incredible in a world where 99% of sources barely achieve two of these goals.

There are three threads. The others are:

Google's post https://news.ycombinator.com/item?id=21332768

IBM's critique https://news.ycombinator.com/item?id=21333105

I still don't understand what the hell is "quantum computing". I think my problem is my own conception of classical computing.

My best approximation for what a quantum computer actually is. Is that it's some sort of device to set quantum states, then run a "quantum algorithm" (i.e. a graph of "quantum logic gates"), and finally read out the "quantum bits" resulting from the algorithm. That sounds a lot more like a sensor to me. Also all the problems with noise and calibration reinforce my notion that it's more like a sensor than a computer.

But to be fair I barely understand "classical computing". I think my personal notion relies too much on badly defined ideas about "the run-time" of a computer program (some software) that I have constructed from "industry" experience.

To me big huge fundamental part of computing has to do with arbitrarily representing anything with a symbolic alphabet. And then automatically manipulating this symbolic alphabet to get a result with can be "mapped back" through the initial arbitrary representation so we learn something about whatever we initially chose to represent.

Maybe that's not computing? but then what is that? and then what is computing??

Try as I might I cannot reconcile my understanding of classical computing with quantum computing.

Here's a youtube video that might be at just the right level for you: https://www.youtube.com/watch?v=ZoT82NDpcvQ . Basically it goes over the simplest quantum-vs-classical query advantage (1 instead of 2) that was ever found.

Is that different than a regular computer? To take your statement and slightly modify it:

some sort of device to set electromagnetic charges, then run an "electromagnetic algorithm" (i.e. a graph of "electromagnetic logic gates"), and finally read out the "sequence of electromagnetic bits" resulting from the algorithm.

That sounds to me like the computer that I am typing on now. Am I missing something here?

> Is that different than a regular computer

Not very. Using their definition, logic gates, RAM, Flash or Hard Disks could all be redefined as "sensors".

I'd recommend Charles Petzold's Code: http://www.charlespetzold.com/code/

Which does a great job building up computing from bits all the way to a adders, CPUs, and assembly language (with the historical background around it too).

I think the easiest way to get an idea for Quantum Computing and what the difference is comes from watching a specific example, I thought this example of Shor's algorithm was pretty good: https://www.youtube.com/watch?v=wUwZZaI5u0c

Quick explanation.

Flipping a bit in classical computing is an irreversible operation, and so has to release heat. We also have to be in one state at a time.

In quantum computing, we are only allowed reversible operations, but can be in a superposition of states. There is no heat released, no upper limit on how fast the operations can go, and no upper limit on parallelism. But the flip side is that you cannot peek at the operation, and error correction is not exactly easy.

The "only reversible operations" bit is a huge restriction. For example it means that "if" statements are not allowed.

If you really want to know: https://quantum.country/qcvc (previous discussion: https://news.ycombinator.com/item?id=19426573)

If you can't formally differentiate a computer from a sliding rule, you will have problems differentiating a quantum computer from a sensor too. That's normal.

The difference is more on the flexibility to run different programs than on them transforming encoded data. Both a sliding rule and a sensor do transform encoded data, a computer is something that can apply any mathematical transformation into the data.

Nitpick, but there are some transformations that our current computers (or our current mathematics moreso) cannot do, for example, a continuous form of the Fourier Transform. We only possess discrete formulations of it. But in nature, light passing through a prism or diffraction grating performs an equivalent operation (presumably) continuously. So as of right now, nature is still more powerful than our strongest computers.

Well technically the photons only interact in "quanta" themselves anyway. And suddenly we're back at the level of quantum computing!

I'm not sure what transformations you have in mind that "our current mathematics" cannot do.

Overly simplified, but in classical computing, a bit is an abstraction representing a 0 or 1. In quantum computing, a bit IS the electron (or some other particle). And electrons are weird and can behave in very surprising ways. Quantum computers are controlling these electrons allowing to do things that classical computers can't. One example of such thing is Shor's algorithm which, taken from wikipedia, "is almost exponentially faster than the most efficient known classical factoring algorithm".

In classical computing, a bit is a binary state. The implementation isn't important. What is important is there are only two positions: true/false, on/off, electricity flowing/no electricity flowing, a wooden stick pointed to the left/right. If you treat combinations of state as binary numbers (0000=0, 0001=1, 0010=2, 0011=3, etc) and you create functions that manipulate these bits (AND, OR, NOT, etc gates) such that they generate new patterns of bits consistent with doing math. A classical computer relies on classical physics: something exactly is something. You either have a 1 or 0, because the implementation is either one thing or the other thing.

Quantum computing relies on quantum effects, say the spin of an electron. The spin of the electron can be measured and when does it will either be up or down. At first it seems like it's just like a classical computer; however, it's possible to "entangle" multiple qbits together. The orientation becomes fuzzy. In this fuzzy state is possible to create quantum gates that again do math, but these results become "fuzzy."

So I create the function: "Give x such that x has the reminder of 1 after dividing by some huge number?" In classical physics there is no one answer to modulus. There could be an infinite number of possible answers. Solving it with a classical computer does not mean much more than trying values and seeing what works. But, asking that question with a quantum computer does something different.

Being "fuzzy," it exists across all possible states at the same time until you measure it. When you measure it, you will get a random answer but that answer will work for the equation. Say you ask the question, "Give me x where x divided by 5 has a remainder of 1." The quantum computer might first spit out 56 then next time 91 then next time 6.

Your answer is a good one for helping to understand the problem and is true of almost all computers in active use today. But I want to point out that you can have a classical computer that isn't binary. Analog computers have a long history and are still used in some places today. Also ternary computers where bits can be 1, 0, or -1 had a role in Soviet computing and let you used Balanced Ternary[1] which is even nicer than Two's Complement. But these are classical in the sense of having one particular value in the way the rest of your answer lays out nicely.

[1]https://en.wikipedia.org/wiki/Balanced_ternary

> however, it's possible to "entangle" multiple qbits together. The orientation becomes fuzzy. In this fuzzy state is possible to create quantum gates that again do math, but these results become "fuzzy."

The fuzzy results, in my understanding, are a property of quantum mechanics and don't require multiple qubits. A single electron has some probability of spinning up and a complementary probability of spinning down, and until you go ahead and measure the spin, the actual spin value hasn't coalesced to either of those states, instead being some fuzzy intermediate probability spectrum.

Entangling multiple particles means (again, as far as I understand) that their measurements cease to be independent -- if I have several pairs of entangled electrons all with spin of 50% up / 50% down, then I might expect the results of measuring the spin of those pairs to look something like this table:

    +/+   25%
    +/-   25%
    -/+   25%
    -/-   25%

when in fact, because these are entangled pairs, I will either get

    +/+   50%
    +/-   0
    -/+   0
    -/-   50%

    +/+   0
    +/-   50%
    -/+   50%
    -/-   0

What am I missing here?

> What am I missing here?

I am unsure what you are missing because what you explained is approximately correct.

Minor correction:

Entangled qubits (each of 50% propbaility to be up) can have more possible measurement distributions that the two you mentioned.

Distributions like the following exist.

    +/+ 20%
    +/- 30%
    -/+ 30%
    -/- 20%

> if I have several pairs of entangled electrons all with spin of 50% up / 50% down, then I might expect the results of measuring the spin of those pairs to look something like this table:

I think you may misunderstand how to get qubits entangled. You would have to pass two qubits through a two-qubit gate to get them entangled. And doing so would leave you with only one measurement distribution.

For example if you have a qubit in 50% |1>, 50% |0> and pass it through CNOT with a qubit in |1>. You get:

But if the second qubit was in state |0>, you get

> if I have several pairs of entangled electrons all with spin of 50% up / 50% down

Also just in case you don't know qubits have phase so there is more than one way to have a qubit that when measured will be up 50% of the time.

My goal wasn't to explain a "correct" view quantum physics, only to demonstrate at a cursory level that a binary computer's bits differs from a quantum computer's qbits. Quantum physics is not intuitive and attempting to use a classical understanding of probability will get you in trouble. I highly suggest looking at videos on YouTube, which have a far better explanations on the actual behavior of quantum computation. This is a very good video on Bell's Inequality: https://www.youtube.com/watch?v=zcqZHYo7ONs&t=856s

A really important thing to keep in mind is that different possible states have amplitudes, which are complex numbers. These are the real, fundamental description of the system, rather than the probabilities, which are real numbers.

The state of the system could be, for example:

   State  Amplitude  Probability
    +/+      1/2         1/4
    +/-     -1/2         1/4
    -/+     -i/2         1/4
    -/-      i/2         1/4

In the right-hand column, I've included the probability of measuring each state (notice that it's the square of the modulus of the amplitude), but that's not the fundamental quantity that you deal with in quantum mechanics.

All the dynamics of a quantum system are expressed in terms of how the amplitudes change over time. In fact, if this means anything to you, the most succinct way to state how quantum mechanics works is that a quantum system with N possible states is represented by an N-dimensional complex vector, and that in an infinitesimal time step dt, the system goes from v to (1+iHdt)v, where H is a matrix with complex entries (and 1 stands for the identity matrix). If you measure the quantum system, you have to first pick a set of basis vectors in which to measure it. The result you get is one of the basis vectors. The probability of getting any basis vector as result is the square of the coefficient (technically, the square modulus of the coefficient) on that basis vector. The coefficient is what we call the "amplitude."

In a quantum computer, you first prepare the system in a desired state (a complex vector). Then, you get to choose what linear operations you will apply to the state. Then, you observe the state in some basis (in the complex vector space), and get a random basis vector (proportional to the modulus squared of the coefficients in the final state). That's basically it. The trick is whether or not you can actually figure out a way to compute anything useful with such a system with lower complexity than you can with a classical computer. Your fundamental operations are different (linear transformations of a complex vector) than they are in a classical computer, and you have the added wrinkle that you can't read off the final state of the computer - the final result is a random draw from a probability distribution that is based on the state of the computer. Peter Shor figured out that with this setup, you can factor large numbers in a way that uses fewer operations than a classical computer (asymptotically). It also turns out that you can simulate quantum systems really effectively with this sort of system. That's not so surprising. As Feynman said,

> "Nature isn't classical, dammit, and if you want to make a simulation of Nature, you'd better make it quantum mechanical, and by golly it's a wonderful problem, because it doesn't look so easy."

As wild as it sounds, parallel universes are IMO the best way to explain a quantum computer. I posted an article about it:

https://news.ycombinator.com/item?id=21337739

In the end a classical computer just "processes" data. It takes data in, processes it (math operations), then outputs it. The foundation is boolean math, which is then used to execute regular math.

At the very most basic level a computer is made of transistors that can solve the problem of basic boolean math. Gates are AND (or NAND), OR, XOR etc.

An XOR gate produces the following output from the following inputs:

A B Output

0 0 0

0 1 1

1 0 1

1 1 0

an AND gate produces the following outputs:

A B Output

0 0 0

0 1 0

1 0 0

1 1 1

with those gates you can make an adder. A single bit adder has the following inputs and outputs

A B Output 1 Output 2

0 0 0 0 (decimal 0)

1 0 0 1 (decimal 1)

0 1 0 1 (decimal 1)

1 1 1 0 (decimal 2)

Notice that Output 2 is an XOR of inputs A and B Output one is an AND of inputs A and B. So a single bit adder is simply the inputs feeding an XOR gate and an AND gate.

This can be scaled up to add any number of bits. Other math operations can also be done.

Transistors can be used to make memory bits that hold its state and can be set and unset. They are essentially binary gate loops that feed outputs back to inputs and rely on the delay of electron flows to reach stable states.

A clock is used to sequentially count (and pull instructions from memory) and set and unset memory bits. Each cycle of the clock allows the computer to execute the next instruction (by incrementing a number that determines which instruction to fetch).

From there you are right, the bits are used to encode meaning. Which could be alphabets, images, audio etc.

A quantum computer is "a sensor" in the same sense that every laptop is "an electronics experiment".

A quantum computer still fits your model because you arbitrarily represent anything with an alphabet of quantum states, automatically manipulate it with a quantum algorithm, and map back the result at the end so we learn something about whatever. I do not see the contradiction.

Minute Physics has a really good explanation of Shor's algorithm, and by proxy, Quantum computing. https://www.youtube.com/watch?v=lvTqbM5Dq4Q

And the followup: https://www.youtube.com/watch?v=FRZQ-efABeQ

http://archive.is/3ajcQ

Thx! Blog is already down for me.

He might just need a static-site blog from this point on.

So assuming that people take the economic loss and switch to public key encryption schemes that appear quantum hardened what's the next most interesting thing to do with a quantum computer?

Quadratic speedup over any black box function is pretty nice. Could certainly help ML a lot.

Could you elaborate? If the function is XOR I'm pretty sure you won't see a speed up

He's referring to Grover's algorithm.

> we cared about the increase in the speedup as D-Wave upgraded its hardware, and the trouble was that we never saw a convincing case that there would be one.

Is D-Wave still doing useful work in the field?

I've been meaning to read up on them and recent progress quantum in general... I still see D-Wave in the news often in the tech press and Canadian media.

Scott Aaronson is probably one of the most underrated scientists of our time. He's very approachable and has responded to comments and emails of undergrads like me in a few hours. Not only is he part of the team that practically invented quantum supremacy, but his blog is the most informative blog out there for ethics, morality, nerdiness, theoretical computer science and the philosophical implications of complexity theory.

Y Combinator had a podcast with him which you can watch here: https://www.youtube.com/watch?v=0jrybODBUpA

I enjoy Aaronson's blog/interviews, but he is not an "underrated scientist", he is perhaps an underrated science communicator. Being a science communicator, however, is somewhat unrelated to being a scientist. Looking at his actual scientific work, he is in fact doing good work, but he is not in the same league as, let's say, Peter Shor.

I think his BosonSampling method comes very close to Shor's algorithm, and I don't think "leagues" really exist in academic output - but he's not doing good work - he's doing great work.

Reply on news.ycombinator.com