Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1509.06183 · Nature Communications

Provable quantum advantage in randomness processing

Howard Dale, David Jennings, Terry Rudolph

Published Sep 18, 2015• 39 citations
arXivHTMLPDF

Abstract

Quantum advantage is notoriously hard to find and even harder to prove. For example the class of functions computable with classical physics exactly coincides with the class computable quantum mechanically. It is strongly believed, but not proven, that quantum computing provides exponential speed-up for a range of problems, such as factoring. Here we address a computational scenario of randomness processing in which quantum theory provably yields, not only resource reduction over classical stochastic physics, but a strictly larger class of problems which can be solved. Beyond new foundational insights into the nature and malleability of randomness, and the distinction between quantum and classical information, these results also offer the potential of developing classically intractable simulations with currently accessible quantum technologies. Although quantum alternatives of various classical tasks are considered advantageous, this is typically extremely difficult to concretely prove. Here, the authors show that a quantum approach to randomness processing provides a reduction in resources and a larger class of solvable problems.

DOI
10.1038/ncomms9203

Related papers

Quantum Advantage in Shared Randomness Processing

Tamal Guha, Mir Alimuddin, Sumit Rout +3 more

Randomness appears both in classical stochastic physics and in quantum mechanics. A number of communication models and other information protocols entail sharing randomness among distant parties. Here we report a computational scenario of shared randomness processing where quantum sources manifest clear-cut precedence over the corresponding classical counterparts. The advantage is established in a resource theoretic set-up which we formalize in this work. The classical mutual information turns out to be a faithful resource quantifier of shared randomness although it does not sufficiently characterize all possible transitions among the resources. Quantum theory exhibits advantage in shared randomness processing in the sense that the set of resourceful states obtained under free operation from a bipartite quantum system is strictly larger than the set obtained from an analogous classical system. Interestingly, the quantum advantage can be manifested in the optimal payoff of a two players co-operative game -- the `non-monopolize social subsidy' game. We also show that the quantum states resulting to the desired advantage necessitates nonclassicality in the form of quantum discord. We then address the task of distributing shared randomness between two parties. Quite interestingly, it turns out that noisy quantum channel can exhibit advantage even when it has zero quantum capacity and classical capacity much less than the corresponding classical channel. The imperfect channel examples facilitates and welcomes experiment to achieve the reported quantum advantage with presently available quantum devices.

•Jan 7, 2020•0 citations

Quantum coins and quantum sampling

Howard Dale

Quantum computing is rapidly becoming one of the largest research areas in quantum physics and yet we are still unable to prove the superiority of quantum computing over classical with the exception of a few contrived and unrealistic scenarios. Understanding the areas in which quantum computing provides an advantage and, more importantly, where that advantage comes from is the key to making progress in the field. We certainly do not solve this mystery in this thesis but do explore some unconventional routes through which answers may be found in the future. To this end we explore quantum advantage in a different computational setting. Rather than working with Turing Machines as most research does, we focus on the Bernoulli Factory: a randomness processing scheme studied in the fields of statistics and computer science. The Bernoulli Factory takes an infinite string of random bits generated with a fixed unknown bias as input and outputs a single random bit, the bias of which is a function of the input bias. This can be seen more intuitively as generating one biased coin from another, given a desired relationship between the two biases. The Bernoulli Factory is inherently probabilistic, like quantum mechanics, and so, it leads us to questions about the fundamental nature of quantum randomness and quantum sampling. We find, as we hoped, that the Bernoulli Factory is more tractable than the Turing Machine and that we are able to prove quantum superiority in both resource efficiency and classes of computable functions. We first give the quantum analogue of the classical Keane-O'’Brien theorem which establishes the increased class of computable functions for the quantum case. We then adjust the problem in a variety of ways, such as introducing multiple coins, errors in state preparation, phases and restriction on the bias or operations allowed. These lead to additional results which lend insight into the problems faced in quantum computing as well as the nature of quantum randomness.

•Sep 1, 2016•0 citations

Quantum Advantage in Resource Estimation

William A. Simon, Peter J. Love

Quantum computing promises the ability to compute properties of quantum systems exponentially faster than classical computers. Quantum advantage is achieved when a practical problem is solved more efficiently on a quantum computer than on a classical computer. Demonstrating quantum advantage requires a powerful quantum computer with low error rates and an efficient quantum algorithm that has a useful application. Despite rapid progress in hardware development, we still lack useful applications that are feasible for the next generation of quantum computers. Here we argue that an exponential quantum advantage exists in producing numerical resource estimates of larger quantum algorithms by accurately measuring simulation errors. We provide a quantum algorithm for measuring simulation errors of Trotter-based algorithms. Our results indicate that this method will reduce runtimes of quantum algorithms by approximately three orders of magnitude for one-hundred qubit systems. We also predict that these reductions will increase with system size. The methods we propose require relatively few qubits and operations, meaning the next generation of quantum computers could compute simulation errors for classically intractable systems. Since the underlying computations that lead to reduced resource estimates are infeasible for classical computers, this task is a candidate for demonstrating practical quantum advantage.

quant-pharXiv:2512.02131•Dec 3, 2025•0 citations

Exponential quantum advantages in learning quantum observables from classical data

Riccardo Molteni, Casper Gyurik, Vedran Dunjko

Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that $$BQP$$ B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.

arXiv:2405.02027•npj Quantum Information•Jan 10, 2026•6 citations

Quantum methods for machine learning and classical dynamics

Alice Barthe

All the data stored and processed by our computers is encoded as sequences of zeros and ones, called bits. Quantum computers offer an alternative to this traditional way of encoding and manipulating information. The information in a collection of qubits can be a combination, also called a superposition, over many possible sequences of zeros and ones. Where classical computation consists of flipping zeros and ones, quantum computation consists of manipulating high-dimensional vectors called quantum states. Researchers have found ways to use this to engineer quantum algorithms that solve some tasks much faster than any classical computer would. These are called quantum advantages, and are proven for specific tasks, such as breaking some encryption schemes and solving certain large linear systems. The goal of this thesis was to find new tasks for which quantum computers provably have an advantage over classical computers. In this thesis, I present two such advantages and associated results. The first one revolves around a physically relevant learning task. In other words, I explore how quantum computers can be used to help solve specialized machine learning tasks. The second one addresses the simulation of classical systems. One of the first high-potential and natural uses of quantum computers was the simulation of quantum systems. A lot of real-world problems, however, are ruled by classical physics. It turns out that quantum computers are well suited for the simulation of some exponentially large classical systems. In this thesis, I add a new problem to this list.

•Mar 26, 2026•0 citations

Quantum supremacy: some fundamental concepts

Man‐Hong Yung

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!

National Science Review•Jul 4, 2018•22 citations
Quantum advantage is notoriously hard to find and even harder to prove. For example the class of functions computable with classical physics exactly coincides with the class computable quantum mechanically. It is strongly believed, but not proven, that quantum computing provides exponential speed-up for a range of problems, such as factoring. Here we address a computational scenario of randomness processing in which quantum theory provably yields, not only resource reduction over classical stochastic physics, but a strictly larger class of problems which can be solved. Beyond new foundational insights into the nature and malleability of randomness, and the distinction between quantum and classical information, these results also offer the potential of developing classically intractable simulations with currently accessible quantum technologies. Although quantum alternatives of various classical tasks are considered advantageous, this is typically extremely difficult to concretely prove. Here, the authors show that a quantum approach to randomness processing provides a reduction in resources and a larger class of solvable problems.
Randomness appears both in classical stochastic physics and in quantum mechanics. A number of communication models and other information protocols entail sharing randomness among distant parties. Here we report a computational scenario of shared randomness processing where quantum sources manifest clear-cut precedence over the corresponding classical counterparts. The advantage is established in a resource theoretic set-up which we formalize in this work. The classical mutual information turns out to be a faithful resource quantifier of shared randomness although it does not sufficiently characterize all possible transitions among the resources. Quantum theory exhibits advantage in shared randomness processing in the sense that the set of resourceful states obtained under free operation from a bipartite quantum system is strictly larger than the set obtained from an analogous classical system. Interestingly, the quantum advantage can be manifested in the optimal payoff of a two players co-operative game -- the `non-monopolize social subsidy' game. We also show that the quantum states resulting to the desired advantage necessitates nonclassicality in the form of quantum discord. We then address the task of distributing shared randomness between two parties. Quite interestingly, it turns out that noisy quantum channel can exhibit advantage even when it has zero quantum capacity and classical capacity much less than the corresponding classical channel. The imperfect channel examples facilitates and welcomes experiment to achieve the reported quantum advantage with presently available quantum devices.
Quantum computing is rapidly becoming one of the largest research areas in quantum physics and yet we are still unable to prove the superiority of quantum computing over classical with the exception of a few contrived and unrealistic scenarios. Understanding the areas in which quantum computing provides an advantage and, more importantly, where that advantage comes from is the key to making progress in the field. We certainly do not solve this mystery in this thesis but do explore some unconventional routes through which answers may be found in the future. To this end we explore quantum advantage in a different computational setting. Rather than working with Turing Machines as most research does, we focus on the Bernoulli Factory: a randomness processing scheme studied in the fields of statistics and computer science. The Bernoulli Factory takes an infinite string of random bits generated with a fixed unknown bias as input and outputs a single random bit, the bias of which is a function of the input bias. This can be seen more intuitively as generating one biased coin from another, given a desired relationship between the two biases. The Bernoulli Factory is inherently probabilistic, like quantum mechanics, and so, it leads us to questions about the fundamental nature of quantum randomness and quantum sampling. We find, as we hoped, that the Bernoulli Factory is more tractable than the Turing Machine and that we are able to prove quantum superiority in both resource efficiency and classes of computable functions. We first give the quantum analogue of the classical Keane-O'’Brien theorem which establishes the increased class of computable functions for the quantum case. We then adjust the problem in a variety of ways, such as introducing multiple coins, errors in state preparation, phases and restriction on the bias or operations allowed. These lead to additional results which lend insight into the problems faced in quantum computing as well as the nature of quantum randomness.
Quantum computing promises the ability to compute properties of quantum systems exponentially faster than classical computers. Quantum advantage is achieved when a practical problem is solved more efficiently on a quantum computer than on a classical computer. Demonstrating quantum advantage requires a powerful quantum computer with low error rates and an efficient quantum algorithm that has a useful application. Despite rapid progress in hardware development, we still lack useful applications that are feasible for the next generation of quantum computers. Here we argue that an exponential quantum advantage exists in producing numerical resource estimates of larger quantum algorithms by accurately measuring simulation errors. We provide a quantum algorithm for measuring simulation errors of Trotter-based algorithms. Our results indicate that this method will reduce runtimes of quantum algorithms by approximately three orders of magnitude for one-hundred qubit systems. We also predict that these reductions will increase with system size. The methods we propose require relatively few qubits and operations, meaning the next generation of quantum computers could compute simulation errors for classically intractable systems. Since the underlying computations that lead to reduced resource estimates are infeasible for classical computers, this task is a candidate for demonstrating practical quantum advantage.
Abstract Quantum computers are believed to bring computational advantages in simulating quantum many-body systems. However, recent works have shown that classical machine learning algorithms are able to predict numerous properties of quantum systems with classical data. Despite examples of learning tasks with provable quantum advantages being proposed, they all involve cryptographic functions and do not represent any physical scenarios encountered in laboratory settings. In this paper, we prove quantum advantages for the physically relevant task of learning quantum observables from classical (measured-out) data. We consider two types of observables: first, we prove a learning advantage for linear combinations of Pauli strings, then we extend our results to a broader case of unitarily parametrized observables. For each case, we delineate sharp boundaries separating physically relevant tasks that admit efficient classical learning from those for which a quantum computer remains necessary for data analysis. Unlike previous works, our classical hardness results rely only on the weaker assumption that BQPBQPBQP B Q P hard processes cannot be simulated by polynomial-size classical circuits, and we also provide a nontrivial quantum learning algorithm. Our results clarify when quantum resources are useful for learning problems in quantum many-body physics, and suggest practical directions in which quantum learning improvements may emerge.
All the data stored and processed by our computers is encoded as sequences of zeros and ones, called bits. Quantum computers offer an alternative to this traditional way of encoding and manipulating information. The information in a collection of qubits can be a combination, also called a superposition, over many possible sequences of zeros and ones. Where classical computation consists of flipping zeros and ones, quantum computation consists of manipulating high-dimensional vectors called quantum states. Researchers have found ways to use this to engineer quantum algorithms that solve some tasks much faster than any classical computer would. These are called quantum advantages, and are proven for specific tasks, such as breaking some encryption schemes and solving certain large linear systems. The goal of this thesis was to find new tasks for which quantum computers provably have an advantage over classical computers. In this thesis, I present two such advantages and associated results. The first one revolves around a physically relevant learning task. In other words, I explore how quantum computers can be used to help solve specialized machine learning tasks. The second one addresses the simulation of classical systems. One of the first high-potential and natural uses of quantum computers was the simulation of quantum systems. A lot of real-world problems, however, are ruled by classical physics. It turns out that quantum computers are well suited for the simulation of some exponentially large classical systems. In this thesis, I add a new problem to this list.
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!