Hacker News Reader

Comment by thoweruo34 | Hacker News Reader

Thanks for this perspective. I've always thought the whole "yay! let's do quantum programming!" was a bit strange. IIRC we can't really do "real" quantum computation with anything more than a few bits because people can't do QEC to correct for the noise. D-Wave's systems aren't even "real" QCs AFAIK.

From a very amateur perspective, it looked like Gil Kalai was arguing that physical realizations would not be impossible, but work at UIST and Google's "quantum supremacy" result, somehow have proved him wrong ?

Can you say a bit more on the state of QEC ? Thanks.

P.S: The hype of CS these days is really getting tiring; the ridiculuous expectations around "quantum-deeplearning-crypto-neuron-RL" will hopefully not cause another AI winter.

View on HN

> From a very amateur perspective, it looked like Gil Kalai was arguing that physical realizations would not be impossible, but work at UIST and Google's "quantum supremacy" result, somehow have proved him wrong ?

I assume you meant "would be impossible"? At any rate, from my slightly less amateurish understanding of the subject, I think that the main contrast between Kalai's claims and Google's results boils down to the following:

- broadly speaking, Kalai is referring to pure quantum computation, more specifically he is computing limits about the efficiency and energy requirements of computers that work exclusively using quantum/linear logic;

- Google's experiment made extensive use of classical computation, and it's unclear to what extent quantum computation actually impacted the result (to the point that some people claim that the entire experiment could be performed classically, see e.g. [1])

Unfortunately, many of the nuances in the debate are lost on me--in the past, I had some forays into the physics and mathematics of QC but was ultimately driven away from the dumb money flowing around--but I would recommend Gil Kalai's blog [2] as it is both accessible and rigorous (albeit being obviously biased toward one side of the argument).

[1] https://arxiv.org/abs/2103.03074

[2] https://gilkalai.wordpress.com/

> Can you say a bit more on the state of QEC ? Thanks.

There's not a lot I can say other than what's (I think) more or less common knowledge in the field: QEC is a practical issue, and so is deeply tied to physical implementation, etc. QC however, as an idea, has power in itself; you can define a Turing-like machine that incorporates notions of quantum mechanics, forming complexity classes that are thought to be disjoint from the classical ones (including probabilistic classical machines) (see ref. [2] in the OP). QEC is, then, any strategy that allows you to implement reliable (QC) resources in practice (think classical redundancy). The fact that you are dealing with quantum resources rather than classical makes it harder than CEC. The problem with current technology is that if you don't have QEC you can't really get to a point (resource-wise) where the classical/quantum class separation is relevant. Achieving this separation is what's called "supremacy" (or "advantage"). You can try to sidestep QEC by building quality (as noiseless as possible) quantum computers.

Quantum supremacy is debated, and so not something I can reasonably comment on. From the explanation above however, you can see that supremacy is achieved whenever you do something with a QC that cannot be done with a classical computer. The problem is proving that something is 100% provably beyond the scope of a classical computer (people are clever, and so it's often not). However, one thing is to say whether people are achieving quantum supremacy, another is to say whether people are doing quantum computing. For the latter, I would say we definitely are. You can definitely access a quantum computer in the cloud and run routines that can only produce the given outcome if there are quantum effects in play. [1] (Whether or not you could simulate these results classically relates to supremacy, not whether QC is real.)

[1] https://quantum-computing.ibm.com/composer/docs/iqx/guide/en...

> Quantum supremacy is debated, and so not something I can reasonably comment on. From the explanation above however, you can see that supremacy is achieved whenever you do something with a QC that cannot be done with a classical computer. The problem is proving that something is 100% provably beyond the scope of a classical computer (people are clever, and so it's often not).

My understanding was that quantum supremacy occurs when a quantum computer performs a computation that cannot be performed with comparable speed on a classical computer given the best available classical hardware and the best available classical algorithms of the time. In particular, it does not require a proof that no efficient classical algorithm exists. Instead, it is sufficient that nobody knows such a classical algorithm at the time of demonstration.

Otherwise even factoring a large number by running Shor's algorithm on an error corrected quantum computer would still not constitute quantum supremacy demonstration because there is no proof that factoring cannot be done efficiently on a classical computer. After all, it is not inconceivable that people just don't know how to factor integers fast on a classical computer.

I agree, but the argument holds --- in particular I'm thinking of Google's supremacy experiment, where they did do something that, taken as a generic process, would require resources beyond "the best available classical hardware and the best available classical algorithms of the time". However, people play catch-up, and end up coming up with classical approaches for that particular experiment. Of course, factoring is a special and very strong case that is less susceptible to this.

Reply on news.ycombinator.com