Quantum Computing
Quantum computers are expected to be better at solving certain computational problems than classical computers. This expectation is based on (well-founded) conjectures in computational complexity theory, but rigorous comparisons between the capabilities of quantum and classical algorithms are difficult to perform. Bravyi et al. proved theoretically that whereas the number of “steps” needed by parallel quantum circuits to solve certain linear algebra problems was independent of the problem size, this number grew logarithmically with size for analogous classical circuits (see the Perspective by Montanaro). This so-called quantum advantage stems from the quantum correlations present in quantum circuits that cannot be reproduced in analogous classical circuits.
Science , this issue p. [308][1]; see also p. [289][2]
[1]: /lookup/doi/10.1126/science.aar3106
[2]: /lookup/doi/10.1126/science.aau9555
Quantum Computing
Quantum computers are expected to be better at solving certain computational problems than classical computers. This expectation is based on (well-founded) conjectures in computational complexity theory, but rigorous comparisons between the capabilities of quantum and classical algorithms are difficult to perform. Bravyi et al. proved theoretically that whereas the number of “steps” needed by parallel quantum circuits to solve certain linear algebra problems was independent of the problem size, this number grew logarithmically with size for analogous classical circuits (see the Perspective by Montanaro). This so-called quantum advantage stems from the quantum correlations present in quantum circuits that cannot be reproduced in analogous classical circuits.
Quantum computation was envisioned by Feynman as a valuable means of solving quantum problems [1]. The question is, how do we prove the superiority of quantum computing over classical devices? A common misconception in describing the power of a quantum computer over a classical computer is that quantum bits can be prepared in a superposition of an exponential number of states, which cannot be achieved with classical bits. This statement is certainly true, but it does not tell us, specifically, what problems quantum computers can efficiently solve while classical computers fail to do so. In fact, based exactly on the technique of Feynman's path integral, the output (i.e. transition amplitude) of any quantum circuit can be calculated classically with a polynomial amount of memory (although the temporal cost would be exponential). Therefore any quantum computation can be simulated classically; the key question is about the efficiency. Much effort has been made trying to pin down the power of quantum computers based on the machinery of the computational complexity theory. In particular, the class of computational (decision) problems that can be solved efficiently by a quantum computer is called BQP (bounded-error quantum polynomial time); the counterpart for classical computers is called P (polynomial time). Of course, BQP cannot be less than P; in principle quantum computers can simulate classical computers efficiently. The point is that the foundation of quantum computation cannot be established without a proof showing that BQP is strictly larger than P (i.e. BQP ≠ P). In this sense, this question is as interesting as the famous challenge of proving P ≠ NP (non-deterministic polynomial time). A well known instance of an NP problem is the factoring problem; Shor's quantum algorithm is capable of solving the factoring problem in polynomial time, which is not achievable with the best classical algorithm discovered so far. However, we still cannot rigorously exclude the possibility of the existence of an efficient classical algorithm for factoring. Although again without a proof, it is commonly believed that quantum computers are unable to solve some of the NP problems. In fact, the proof of this statement (if true) provides a possible path to prove P ≠ NP. A potentially less demanding question would be, when do we expect a quantum computer to be able to perform some well defined tasks (not necessarily related to any practical problem) that cannot be simulated with any currently available classical device, within a reasonable time? Once achieved, the status is called ‘quantum supremacy' [2]. One may ask, what about Grover's search algorithm, which provides a quadratic speedup over the classical search? Can we say that we can already achieve quantum supremacy with Grover's algorithm? The problem is that, instead of taking the large-N limit, quantum supremacy requires us to determine the actual number of qubits and gates that can no longer be simulated by classical computers within a reasonable time. To elaborate further, we remark that there can be two notions of classical simulation, namely ‘strong simulation' versus ‘weak simulation'. Strong simulation refers to the cases of calculating the transition probabilities, or expectation values of observables, to a high accuracy in polynomial time. Weak simulation requires the probability distributions to be accurately reproduced, which involves ‘sampling' the different outcomes of the quantum devices. Some quantum circuits that cannot be strongly simulated with an efficient classical means may have efficient classical methods for weak simulation [3]. However, we should be careful about the accuracy requirement in the simulation tasks. For example, for many decision problems, it may be sufficient to determine the transition amplitudes to within an additive error, instead of multiplicative error. In other words, the classical simulability of quantum computational problems depends on the accuracy requirement. Currently, there are three popular approaches for achieving quantum supremacy (see Fig. 1), namely (i) boson sampling [4], (ii) sampling IQP (instantaneous quantum polynomial) circuits [5], and (iii) sampling chaotic quantum circuits [6]. In all of these approaches, distributions of different bit strings or photon numbers are sampled from the quantum devices. Furthermore, they all involve the assumption that classical computers are unable to efficiently determine the transition amplitudes, and/or reproduce (or approximate) the distributions of quantum devices performing these tasks, in the sense of both strong and weak simulations. Three different approaches for achieving quantum supremacy: (a) boson sampling; (b) IQP circuits; (c) chaotic quantum circuits. In boson sampling, single photons are injected into different modes of a linear optical network. The task is to determine the photon distributions at the output ports. The key feature of boson sampling is that the transition amplitudes are related to the permanents of complex matrices, which are in general very difficult to calculate exactly, or approximate to within an multiplicative error; these problems belong to the #P-hard complexity class. Moreover, efficient weak simulation of boson sampling is believed to be impossible, unless the polynomial hierarchy collapses to its third level. However, a recent numerical study suggests that, in order to achieve quantum supremacy with boson sampling, one needs to simultaneously generate at least 50 or more single photons, which is still highly technologically challenging. An interesting question is whether linear optics, in the setting of boson sampling, can be applied to solve decision problems. In this case, the transition amplitudes may need to be determined to an additive error. However, we found that a large class of decision problems associated with boson sampling can be simulated by a classical computer [7], settling an open problem [8] by Aaronson and Hance. IQP circuits represent a simplified quantum-circuit model. The initial state starts from the all-zero state, |000…0〉, followed by applying Hadamard gates to each qubit. Then, diagonal gates are applied to the qubits, followed by applying Hadamard gates to each qubit again. The argument of showing the complexity in simulating IQP circuits is similar to that of boson sampling. In fact, the complexity of boson sampling was inspired by the complexity results of IQP circuits. However, when subject to noise, IQP circuits may become classically simulable [9]. Lastly, chaotic quantum circuits refer to the class of quantum circuits where two-qubit gates are applied regularly, while single-qubit gates are applied randomly from a gate set. The output distributions of these circuits approach the so-called Porter–Thomas distribution, which is a characteristic feature of quantum chaos. Recently, there have been several numerical investigations aiming to explore the ultimate limit of classical computing in simulating low-depth quantum circuits. For the ideal cases, one needs to consider both the qubit number and circuit depth for benchmarking quantum supremacy. However, in the presence of noise, these chaotic circuits may also become classically simulable for high-depth circuits [10]. Finally, other than these three approaches, one should expect that quantum supremacy can be achieved for many practical applications, e.g. simulation of quantum chemistry or quantum machine learning. When will it happen? Only time will tell!
Quantum computing operates by manipulating the quantum state of a system to solve problems intractable for classical computing. These problems, previously considered limitations of classical algorithms, have solutions through quantum approaches. Therefore, quantum computing suggests that the complexity of such problems lies in the current epistemic state rather than the objective state of the problem. Computational complexity can be classified into objective and epistemic complexity. Some classical problems exhibiting exponential complexity fall into the epistemic category, as their solutions depend on the current state of human knowledge and available tools. Quantum computing suggests that even mathematics isn’t entirely objective, and mathematics, in one sense, is human-made and a kind of technology, which reflects our intention and planning. Computational complexity, therefore, bridges the objective and subjective. Overcoming classical complexity necessitates advancements in scientific theories, algorithms, and quantum technology, all of which rely on the development of human cognitive abilities. Quantum computing is not just a mathematical construct, but also has physical meaning. If it were purely mathematical, classical physics and systems could potentially achieve the same results. What makes the quantum world special is its empirical nature—the physical reality of quantum chips, quantum algorithms, and quantum evolution. Quantum supremacy, or quantum advantage, refers to the potential superiority of quantum computers over classical ones. Controllable quantum systems offer an overwhelming advantage in terms of manipulation and dominance compared to classical systems. Essentially, quantum computing has the potential to significantly outperform classical computing. Many experts, including Shor, have proposed that quantum computing’s power stems from its ability to perform multiple computations simultaneously—a concept often referred to as the Quantum parallelism thesis. Rather, some argue that the true source of quantum computing acceleration lies in the fundamental differences between classical and quantum logic. However, it’s important to note that quantum logic, while providing a new perspective, does not directly address the core principle of quantum parallelism. This dominance stems from quantum physics’ unique properties: Exponential storage capacity, parallel computing inherent to its nature (ontological), and the ability to perform calculations with exponential speedup through quantum algorithms.
Quantum Computing
Quantum computational advantage or supremacy is a long-anticipated milestone toward practical quantum computers. Recent work claimed to have reached this point, but subsequent work managed to speed up the classical simulation and pointed toward a sample size–dependent loophole. Quantum computational advantage, rather than being a one-shot experimental proof, will be the result of a long-term competition between quantum devices and classical simulation. Zhong et al. sent 50 indistinguishable single-mode squeezed states into a 100-mode ultralow-loss interferometer and sampled the output using 100 high-efficiency single-photon detectors. By obtaining up to 76-photon coincidence, yielding a state space dimension of about 1030, they measured a sampling rate that is about 1014-fold faster than using state-of-the-art classical simulation strategies and supercomputers.
Science , this issue p. [1460][1]
[1]: /lookup/doi/10.1126/science.abe8770
In this thesis we address the question, what is the resource, or property, that enables the advantage of quantum computers?The theory of quantum computers dates back to the eighties, so one would think there already is an answer to this question.There are several proposed solutions, but to this date, there is no consensus on an answer.Primarily, the advantage of quantum computers is characterized by a speedup for certain computational problems.This speedup is measured by comparing quantum algorithms with the bestknown classical algorithms.For some algorithms we assume access to an object called oracle.The oracle computes a function, and the complexity of the oracle is of no concern.Instead, we count the number of queries to the oracle needed to solve the problem.Informally, the question we ask using an oracle is: if we can compute this function efficiently, what else could we then compute.However, using oracles while measuring a quantum speedup, we assume access to vastly different oracles residing in different models of computation.For our investigation of the speedup, we introduce a classical simulation framework that imitates quantum algorithms.The simulation suggests that the property enabling the potential quantum speedup is the ability to store, process, and retrieve information in an additional degree of freedom.We then theoretically verified that this is true for all problems that can be efficiently solved with a quantum computer.In parallel to this, we also see that quantum oracles sharply specify the information we can retrieve from the additional degree of freedom, while regular oracles do not.A regular oracle does not even allow for an extra degree of freedom.We conclude that comparing quantum with classical oracle query complexity bounds does not provide conclusive evidence for a quantum advantage.I want to thank Jan-Åke Larsson, without whom this research would not have been possible.If there is any magic in the world, it shows through Jan-Åke's ability to simultaneously be a good supervisor, colleague, and friend.I would also like to thank my co-supervisor Peter Jonsson, for many valuable discussions -not only restricted to theoretical computer science.To my friends and collogues that have challenged me to become better, especially Jonathan Jogenfors
The generation of certifiable randomness is the most fundamental information-theoretic task that meaningfully separates quantum devices from their classical counterparts. We propose a protocol for exponential certified randomness expansion using a single quantum device. The protocol calls for the device to implement a simple quantum circuit of constant depth on a 2D lattice of qubits. The output of the circuit can be verified classically in linear time, and is guaranteed to contain a polynomial number of certified random bits assuming that the device used to generate the output operated using a (classical or quantum) circuit of sub-logarithmic depth. This assumption contrasts with the locality assumption used for randomness certification based on Bell inequality violation and more recent proposals for randomness certification based on computational assumptions. Furthermore, to demonstrate randomness generation it is sufficient for a device to sample from the ideal output distribution within constant statistical distance. Our procedure is inspired by recent work of Bravyi et al. (Science 362(6412):308-311, 2018), who introduced a relational problem that can be solved by a constant-depth quantum circuit, but provably cannot be solved by any classical circuit of sub-logarithmic depth. We develop the discovery of Bravyi et al. into a framework for robust randomness expansion. Our results lead to a new proposal for a demonstrated quantum advantage that has some advantages compared to existing proposals. First, our proposal does not rest on any complexity-theoretic conjectures, but relies on the physical assumption that the adversarial device being tested implements a circuit of sub-logarithmic depth. Second, success on our task can be easily verified in classical linear time. Finally, our task is more noise-tolerant than most other existing proposals that can only tolerate multiplicative error, or require additional conjectures from complexity theory; in contrast, we are able to allow a small constant additive error in total variation distance between the sampled and ideal distributions.
Spin Models
The idea of finding an all-encompassing model to describe the world around us has appealed to generations of scientists. Although we are very far from this ultimate goal, more modest steps can be taken if we focus on particular problems. De las Cuevas and Cubitt used concepts borrowed from computer science to show that all classical spin models (introduced initially to study magnetism) can be solved by tackling a slightly more complex, universal model (see the Perspective by Wehner). Thanks to these findings, it may be possible to physically simulate systems with complex interactions, using the well-understood two-dimensional Ising model with fields.
Science , this issue p. [1180][1]; see also p. [1156][2]
[1]: /lookup/doi/10.1126/science.aab3326
[2]: /lookup/doi/10.1126/science.aaf0748