However, the outcome of Google’s experiment did not meet all the criteria for proving quantum advantage; for example, the result was not efficiently verifiable on a classical computer. Other well-known work in this field, such as Shor's algorithm, is verifiable but still too complex to run on current quantum hardware. In the recently published scientific paper Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity van Weggemans et al. on arXiv, a new approach to proving quantum advantage is presented, which is classically verifiable in a new setting.
Maximum quantum advantage in a new sample-to-sample problem
Weggemans et al. discovered that quantum computers can achieve maximum quantum advantage for a new type of problem in a so-called ‘sample-to-sample’ setting. This works as follows: a sample is a specific outcome of a random event, given a certain probability distribution over a set of possible outcomes. For example, when throwing a dice, the set of possible outcomes consists of the numbers 1 to 6, the probability distribution assigns each of these outcomes an equal probability, and we call each individual roll a sample. Samples are used in Machine Learning (samples as input, e.g. for training AI models) and in cryptography (samples as output, e.g. keys).
The researchers worked with a slightly different setting in this case: instead of generating as many random samples as possible, they focused on calculating how many input-samples would be needed for producing one single output sample. With this computation they show a situation exists where you can generate a desired output sample with certainty using only one quantum sample, while the number of classical samples needed scales by the order of the total number of possibilities. This proves that in this setting quantum technology can generate the maximum advantage compared to classical technology. Surprisingly, they used a quantum mechanics limitation to prove this: the fact that a measurement generally destroys a quantum state (without the possibility of regaining it).
Experiment can be run on a quantum computer
The study shows the sample-to-sample problem works perfectly for each equal distribution of a set of numbers. They achieved the breakthrough by developing a new quantum algorithm that performs complement sampling by using only one quantum sample and proving that classically the number of samples scales with the total number of possible outcomes. If you can roll a randomly selected half of the numbers from 1 to 1,000,000 with a dice, they show it is possible to change the ‘quantum’ state of this dice into one in which it contains exactly the other half of the numbers (the so-called superposition). One can now perform a simple measure -the quantum equivalent of throwing a dice- and you will receive the outcome instantly. Weggemans: “Because the necessary quantum operations -setting up and switching the quantum dice- we expect this experiment to be executable on a real quantum computer in the near future.” This shows that the sample-to-sample setting quantum technology can do something which is intractable for classical computing technology.”
The research was conducted at the Algorithms & Complexity research group of Centrum Wiskunde & Informatica, the national research institute for mathematics and computer science in the Netherlands, with funding from Quantum Delta NL. Jordi Weggemans will receive his PhD degree on this topic at the UvA during 2025. This paper was created with significant contributions from supervisor Harry Buhrman (former CWI/QuSoft researcher, now Quantinuum) and Marcello Benedetti (Quantinuum).
