Scott’s Supreme Quantum Supremacy FAQ

Preface: I know nothing about quantum computing.

What exactly is a qubit? I'm not asking what does it mean, because I know there's superpositions and all that jazz, but as in...like, in an electronic circuit, what is a qubit? Is it made out of logic gates? Which ones?

If we can make one qubit, can't we just make a bunch of them by copy and pasting circuits similar to how we used vacuum tubes in the 60s and 70s? How come our current limit is only around 54 or so?

Are qubits, and quantum computers by extension, not even electronic circuits? If so...what the hell are they?

If it goes well, the history of quantum computing will be divided up in to three eras: the era of twisty philosophical arguments that it's working ("the molecule is simulating itself"), the era of academic arguments that it's working ("we can solve this one carefully constructed problem") and the era of practical arguments ("Amazon is selling QC time for $20/kilogate-bit, what do you mean it's not possible?"). Quantum supremacy marks the transition from the first era to the second.

Much needed perspective in the age of overly dramatic headlines and straight up misinformation.

I posted this on scott's blog, still awaiting moderation:

"I’m trying to understand the chain of inference from Google’s leaked result of quantum supremacy to theoretical computer-science “hardness” of the computation.

Computing the exact probabilities of a random quantum circuit is proven hard, but computing the exact probability of a random algorithm is also an open problem, so what you really care about is approximation of computing the probability (up to epsilon), or even weaker, just sampling from a probability (also up to epsilon under some metric of comparing distributions).

Their computer implements Random Circuit Sampling, and their cited “theoretical” hardness results are your paper from 2017, of QUATH => HOG, and as far as I understood from your paper, proving that approximation / sampling from a (random) quantum computer/circuit is hard is still an open problem (Am I wrong here? I’m not up to date with everything), and a difficult one. But you did make a compelling argument that even if QUATH was solvable, it will lead to new insights.

Their actual benchmark uses cross-entropy benchmarking, called xeb in their paper, and defined as 2^n* [P(x_i)] _i-1 (Can’t type brackets). I could not find any ‘theoretical hardness’ paper at all using this benchmark, some results talk about different XEB using log but they prove these are not strong enough and can be reached classically.

Are there any hardness results for their benchmark? I wonder why they would use that instead of the proven HOG, even for smaller input sizes, I would see more value in a benchmark which has theoretical roots. I feel intuitively like their benchmark is much more similar to the log variation of XEB than to HOG, but didn’t think it through completely.

As for their gates, I understand they are not general random quantum gates, but instead they have a variation of iSWAP and controlled phase CZ. The hardness results that do exist also don’t address the limited gates, in how it changes the distribution of random circuits. Are those two gates at least universal, so that we have hope that this could be proved? Their statement was “but reliably generating a target unitary remains an active area of research”, so I assume they aren’t universal. I would love to see some heuristic argument as to why those two in particular are hard, especially given results like Gottesman–Knill theorem, it seems like some surprising gates do have classical simulation. iSWAP is just swap and phase gates, and CZ is phase gate only on the 11 state. Doesn’t feel like it could be universal to me but maybe I’m wrong.

I probably missed some things, so I’d love it if you could point to papers filling the gaps between their results and a real theoretical statement. I don’t have the intuition to tell which gaps are important and which are not. I also don’t know which papers/results already exist and I can’t really search as I am not an academic, and don’t have full access to many papers, and you probably know the state of the art results. "

I thought a qubit could also be implemented with current going around a superconductor loop. Is that incorrect?