A World Devoid of �Quantum Computers;�with emphasis on �Predictability and Free Will�
Gil Kalai
Reichman University, New York University and
The Hebrew University of Jerusalem
IDC Herzli
John Conway Spirited Seminar Series
LUMS, Lahore, Pakistan, September 2021
CERN
SESAME
An amazing scientific partnership between Jordan, Cyprus, Egypt, Iran, Israel, Pakistan, the Palestinian Authority, and Turkey
SESAME (Synchrotron-light for Experimental Science and Applications in the Middle East) is a “third-generation” synchrotron light source that was officially opened in Allan (Jordan) on 16 May 2017.
1979: Playing Phutball with John Conway
Overview
It is a serious possibility that quantum computers are not possible. This is what I expect, and I study this possibility since 2005.
Recent claims about quantum supremacy, starting with Google’s 2019 announcement are in tension with my theory. We need to carefully study these claims.
In principle failure of quantum computers has a variety of consequences. Here we will discuss some connections with classical problems in philosophy.
Overview (cont.): The argument against Quantum Computers
Noisy intermediate scale quantum systems (NISQ systems) represent a low-level computational ability that will not allow using them for building quantum error-correcting codes that are needed for quantum computation.
Predictability
Can we predict the future of complex quantum systems in nature?
We consider in parallel two examples:
(A) The Sycamore quantum computer with 12 qubits
(B) Alice (a human being), whose decisions and free will are in question.
Can we build a device M(S) that predicts the behavior of sycamore? Can we build a device M(A) that predicts the behavior of Alice?
My answer: NO!
Free will vs determinism
How to reconcile the apparent facts that
My Answer: (1) There is an ambiguity in the way the future is determined by the past, not in terms of the mathematical laws of physics (which are fully deterministic) but in terms of the physical description of the objects we discuss.
(2) We need to separate between claims about the future that belong to the causal fabric of the past and the future and claims that don’t belong to this fabric
Part I: Background�Computers! (Boolean circuits)
The basic memory component in classical computing is a bit, which can be in two states, “0” or “1”.
A computer (or circuit) has 𝑛 bits, and it can perform certain logical operations on them. The NOT gate, acting on a single bit, and the AND gate, acting on two bits, suffice for the full power of classical computing.
Quantum circuits
Qubits are unit vectors in C2: A qubit is a piece of quantum memory. The state of a qubit is a unit vector in a 2-dimensional complex Hilbert space H = . The memory of a quantum computer (quantum circuit) consists of n qubits and the state of the computer is a unit vector in .
Gates are unitary transformations: We can put one or two qubits through gates representing unitary transformations acting on the corresponding two- or four-dimensional Hilbert spaces, and as for classical computers, there is a small list of gates sufficient for the full power of quantum computing.
Measurement: Measuring the state of k qubits leads to a probability distribution on 0–1 vectors of length k.
Efficient computation and �Computational complexity
NISQ- circuits
Noisy intermediate-scale quantum (NISQ) computers: These are simply noisy quantum circuits with at most 200 (say) qubits.
NISQ devices - near term tasks
Goal 1: Demonstrate quantum supremacy via systems of non-interacting bosons. (Baby goal 1- ten bosons )
Claimed, 2020, USTC’s Jiuzhang
Goal 2: Demonstrate quantum supremacy on random circuits (namely, circuits that are based on randomly choosing the computation process, in advance), with 50–100 qubits. (Baby goal 2 – 10-30 qubits )
Claimed, 2019, Google’s Sycamore + USTC’s
Goal 3: Create distance-5 surface codes on NISQ circuits that require a little over 100 qubits. (Baby goal 3 - distance 3 surface code )
Sycamore
Sycamore is the name of a quantum computer developed by a team from Google. In 2019 it was announced that “quantum supremacy” was achieved via a sample of few million bitstings of length 53.
Putting the supremacy / advantage claims under scrutiny
Can we “spoof” the experimental claims for supremacy/advantage by better classical algorithms?
Are the experimental claims reliable?
The mathematical theory of Noise sensitivity and stability
Boson Sampling �(non interacting bosons)
Troyansky-Tishby (1996), Aaronson-Arkhipov (2010, 2013):
Given a complex n by m matrix X with orthonormal rows. Sample subsets of columns (with repetitions) according to the absolute value-squared of permanents.
This task is referred to as Boson Sampling.
Quantum computers can perform Boson Sampling on the nose. There is a good theoretical argument by Aaronson-Arkhipov (2010) that these tasks are beyond reach for classical computers.
Boson Sampling (permanents):
{1,1} – 0 {1,2} – 1/6 {1,3} – 1/6
{2,2} – 2/6 {2,3} – 0 {3,3} – 2/6
Fermion Sampling (determinants):
{1,2} – 1/6 {1,3} – 1/6 {2,3} – 4/6
Input matrix
1 2 3
Part II: The argument against quantum computers.
(A) Probability distributions described (robustly) by NISQ devices can be described by law-degree polynomials (LDP).
LDP-distributions represent a very low-level computational complexity class well inside (classical) AC0.
(B) In the NISQ regime, asymptotically-low-level computational devices cannot lead to superior computation.
(C) Achieving quantum supremacy is easier than achieving quantum error correction; quantum error correction is not supported by LDP. Therefore, NISQ circuits do not support quantum error correction.
There is strong theoretical evidence for (A) and empirical and theoretical evidence for (C).
(A cartoon from 2017)
Noisy Boson Sampling
(Kalai-Kindler 2014) Let G be a complex Gaussian n x m noise matrix (normalized so that the expected row norms is 1). Given an input matrix A, we average the Boson Sampling distributions over (1-t)1/2 A + t1/2 G.
t is the rate of noise.
Now, expand the outcomes in terms of Hermite polynomials. The effect of the noise is exponential decay in terms of Hermite degree.
The Fourier-Hermite expansion for the Boson Sampling model is beautiful and very simple!
Noise stability/sensitivity of BosonSampling
Boson sampling is technically and conceptually simpler than the circuit model and it allows definite and clear-cut insights that extend to more general models and more complicated situations.
Theorem 1 (Kalai-Kindler, 2014): When the noise level is constant, distributions given by noisy Boson Sampling are well approximated by their low-degree Fourier-Hermite expansion. (Consequently, these distributions can be approximated by bounded-depth polynomial-size circuits.)
Theorem 2 (Kalai-Kindler, 2014): When the noise level is larger than 1/𝑛 noisy boson sampling are very sensitive to noise, with a vanishing correlation between the noisy distribution and the ideal distribution.
The huge computational gap (left) between Boson Sampling (purple) and Fermion Sampling (green) vanishes in the noisy version.
From boson sampling to NISQ systems
Conjecture 3: Both 2014 theorems of Kalai and Kindler extend to all NISQ systems (in particular, to noisy quantum circuits) and to all realistic forms of noise.
(A) Probability distributions described (robustly) by NISQ devices can be described by law-degree polynomials (LDP).
From the point of view of computational complexity, NISQ systems are primitive classical computational devices!
Predictions of near-term experiments �Based on Theorems 1 and 2 and conjecture 3
For the distribution of 0-1 strings based on a quantum pseudo-random circuit, or a circuits for surface code:
a) For a larger amount of noise- you can get robust experimental outcomes, but they will represent LDP (Low Degree Polynomials)- distributions which are far-away from the desired noiseless distributions.
b) For a wide range of a smaller amount of noise- your outcome will be chaotic. This means that the resulting distribution will strongly depend on fine properties of the noise and that you will not be able to reach robust experimental outcomes at all.
(A) The computational power of NISQ systems
NISQ-circuits are computationally very weak, unlikely to allow quantum codes needed for quantum computers.
The crux of the debate
I argue that from the point of view of computational complexity NISQ devices are, in fact, low-level classical computing devices, and I regard it as strong evidence that engineers will not be able to reach the level of noise required for quantum supremacy.
Others argue that the existence of low-level simulation (in the NISQ regime) for every fixed level of noise does not have any bearing on the engineering question of reducing the level of noise.
These sharply different views will be tested in the next few years.
The Fourier connection II
The theory tells us that for samples based on NISQ systems Fourier contributions decay exponentially with the degree.
If we do not witness this behavior in the empirical data, there could be (at least) two explanations
A new remarkable phenomenon in quantum physics.
The familiar phenomenon of biased data selection
Part III: The failure of quantum computation - underlying principles and consequences
Consequences for cats
Following the tradition of using cats for quantum thought experiments, consider an ordinary living cat. In a world devoid of quantum computers.
Here, our “cat” may represent realistic (but involved) quantum evolutions described by sycamore or other quantum circuits with 10-20 qubits.
Lewis Wein (look him up)
Part IV: Predictability and Free Will
https://gilkalai.files.wordpress.com/2021/08/free-will-aug-24.pdf (Hebrew)
A small taste of my argument
We compare the 12-qubit sycamore with a human being Alice.
Unpredictability: The samples of a sycamore computer with 12 qubits cannot be predicted. (And even much more so – Alice’s decisions.) No epistemic determination
Certain future events are not part of the past/future causal fabric. No ontological determinism
Emergent notions: The notion of “Sycamore” that enable predicting is behavior physically meaningless. The correct notion is emergent. And the same for Alice.
Non stationarity (perhaps even chaos) for Sycamore samples
Quantum Key distribution (KCD) �and Conjecture C
Recent news in brief: The famous quantum key distribution (Bennett & Brassard 84) may require for security quantum fault tolerance; If this is the case it is insecure in a world devoid of quantum computers. (Renes & Renner, following Bernstein, and others)
A counterexample Wn claimed by Harrow and Flammia to my “Conjecture C” is possibly incorrect.
Conclusion
While failing to factor many-digit numbers we may gain some insights on predictability and free will.
Understanding noisy quantum systems and potentially even the failure of quantum computers is related to the fascinating mathematics of noise stability and noise sensitivity and its connections to the theory of computing. Exploring this avenue may have important implications to various areas of quantum physics.
Thank you very much!
תודה רבה!
Important analogies�