Comments on: Google Gives A Peek At What A Quantum Computer Can Do

By: Hubert

Hubert — Thu, 20 Jul 2023 01:34:20 +0000

Interesting paper! One major issue is the I/O bottlenecks in quantum machines, that defavor large-data applications, and the other is the type of speedup: quadratic vs exponential. Computational problems that do not require a lot of data I/O, and for which algos provide exponential speedup, or that have a deep oracle (depth >> 1) should run faster on quantum machines: cryptanalysis using Shor’s algorithm, and quantum problems in chemistry and materials science. Also, Simon’s Problem shows exponential speedup, but Grover’s Algorithm is just quadratic.

The Google paper linked in the “That was a key goal …” paragraph of this TNP article focused on cross-entropy benchmarking of noise-induced near-term quantum-decorrelation to identify phase boundaries of some sort (using Random Circuit Sampling — RCS). It seems to conclude that the very large speedup that they obtained (relative to Frontier) is applicable to “certified randomness generation”.

I’m pretty sure that some of my students used this method to answer questions in their mid-term exams!

By: Jon Miciew

Jon Miciew — Wed, 19 Jul 2023 08:26:10 +0000

Anyone hyping quantum superiority should read “Disentangling Hype from Practicality:
On Realistically Achieving Quantum Advantage” https://dl.acm.org/doi/pdf/10.1145/3571725

By: Hubert

Hubert — Tue, 18 Jul 2023 20:00:12 +0000

I find quantum computing to be a fascinating prospect (inasmuch as it may be “fundamental” in the sense of physical reality, and may be needed where process lithography reaches limits related to the size of atoms — if that has anything to do with it), but should readily admit that I do not understand it well, or much, or maybe even at all.

Nevertheless, for the one or two Scheme aficionados ou there, I’d like to point to Choudhury, Agapiev, and Sabry’s 2022 “Scheme Pearl: Quantum Continuations” where they apply delimited first-class continuations to solution of “Simon’s problem” (backtracking search and non-determinism, for decision tree complexity, with exponential oracle separation). It suggests to me that quantum computing might implicitly embody (or seek to exploit) McCarthy’s computational non-determinism, in parallel, within the fluctuating quantum interactions of its qubits.

Irrespective, it is great to see that IBM, Google, Universities, and Labs are competing to impress us with their wherewithal in this domain (and nice article)!