---
title: "Quantum computer solves a problem beyond the reach of classical machines: a new method for verifying quantum advantage"
description: "A new method for verifying quantum advantage has been published in Nature Communications: on the Quantinuum H2 trapped-ion machine, the system solved a task that is statistically unreachable for classical algorithms."
date: 2026-09-08T16:14:00.000Z
lang: en
url: https://xab.info/en/posts/quantum-computer-beats-classical-algorithms-in-new-verification-test
tags: [quantum-computing, quantum-advantage, nature-communications, quantinuum, complement-sampling]
publisher: "XAB.info"
---

# Quantum computer solves a problem beyond the reach of classical machines: a new method for verifying quantum advantage

![Schematic 3D render of a quantum processor with superconducting qubits illustrating a new method for verifying quantum supremacy](https://xab.info/media/2026/09/08/kvantovyi-kompyuter-prevoshel-klassicheskie-algoritmy-v-novom-teste/kvantovyi-kompyuter-prevoshel-klassicheskie-algoritmy-v-novom-teste-1.webp)

## 🎯 Key Points

- A new method for verifying quantum advantage based on a complement sampling task has been published in Nature Communications.
- The experiment was conducted on the Quantinuum H2 trapped-ion quantum computer, scaled up to 55 qubits with thousands of circuits.
- In a test with 37-bit strings, the quantum system solved a task that is statistically unreachable for the best classical algorithms.
- The next step is to separate sampling and analysis onto two quantum computers connected by a quantum communication channel.

An experiment has been published in the scientific journal Nature Communications that proposes a fundamentally new way to confirm that quantum computers can indeed outperform ordinary classical machines. The central problem the work addresses is verification: as the number of operations grows, checking the results of a quantum device on a regular PC becomes practically impossible due to the excessive demands on computational power. The researchers proposed a workaround in the form of an experimental “game” based on a complement sampling task, and the fresh experiment showed that the quantum system handled the task more effectively than the best classical algorithms.

### How the complement sampling “game” works

The essence of the proposed test is simple in formulation but difficult for a classical machine. All possible answer options are secretly divided into two equal groups — A and B. The participant’s goal is to obtain one random option from group A and return an answer belonging to group B. For a classical computer this turns out to be a trap: the system receives only a single specific digit or element and does not know the distribution of the remaining options, so its chances of success drop as the size of the data increases. A quantum computer, by contrast, thanks to superposition can exist in multiple states simultaneously, process the entire group A in parallel, transform it into group B using a special circuit, and only then perform the measurement.

### Why classical machines cannot do this

The difference in approaches leads to a gap in computational efficiency that classical algorithms cannot compensate for by scaling up resources. As the task scales, the classical system faces exponential growth in memory and time requirements, whereas the quantum device uses state parallelism to bypass direct enumeration. This is precisely what makes the proposed test a convenient verification tool: it allows one to pinpoint the moment when the result of a quantum device becomes unreachable for any classical approach, even in theory.

### The 55-qubit experiment

The researchers tested the algorithm on the Quantinuum H2 trapped-ion quantum computer, applying thousands of different circuits and scaling the experiment up to 55 qubits. Despite the presence of hardware noise characteristic of real devices, the quantum system’s results were statistically unreachable for any classical PC. In particular, in a test with 37-bit strings the quantum computer solved a task that lies beyond the capabilities of the best classical algorithms, and the difference in computational efficiency turned out to be substantial.

### What’s next: two quantum computers and a quantum channel

The authors also outline the next stage of the method’s development. In the future they plan to complicate the experiment by separating the answer-selection and answer-analysis systems onto two distinct quantum computers connected by a genuine quantum communication channel. Such a transition from a single device to a distributed configuration will allow verifying advantage under conditions close to real quantum networks and further strengthen the evidentiary basis of verification.

### Context: where this fits in the bigger picture

The obtained result fits into the broader context of the race to prove quantum advantage, where other directions are developing in parallel. For instance, in a related line of work the Jupiter supercomputer previously fully simulated a 50-qubit quantum processor, demonstrating the growing capabilities of classical simulation. It is important, however, that this is a separate achievement and not part of the described experiment: the complement sampling test published in Nature Communications and the 55-qubit experiment on the Quantinuum H2 represent a standalone verification method in which a quantum device solves a task that is statistically unreachable for classical algorithms.

## 🔍 Fact-Check Verification

- [The limits of a PC: a quantum system solved an impossible task](https://www.rbc.ua/ukr/news/mezha-mozhlivostey-pk-kvantova-sistema-virishila-1788873787.html) - Подтверждает публикацию в Nature Communications, метод на основе выборки дополнения, Quantinuum H2 и превосходство над классическими алгоритмами.
- [Quantum computers pass a test that is fundamentally unreachable for classical machines](https://hi-tech.mail.ru/news/155049-kvantovye-kompyutery-proshli-test-nedostupnyi-klassicheskim/) - Согласуется с тем, что тест принципиально недоступен классическим машинам; совпадает с описанием верификационного эксперимента.
- [A major milestone. A quantum computer crushes the classical one in a mathematical game](https://techno.nv.ua/popscience/kvantovaya-verifikaciya-novyy-test-podtverdil-prevoshodstvo-kvantovyh-kompyuterov-50639506.html) - Подтверждает формулировку «математической игры» и результат превосходства квантового компьютера.
- [Supercomputer Jupiter fully simulates a 50-qubit quantum processor for the first time](https://www.ixbt.com/news/2025/11/12/superkompjuter-jupiter-vpervye-polnostju-smodeliroval-50kubitnyj-kvantovyj-processor.html) - Отдельная смежная работа (ноябрь 2025): симуляция 50-кубитного процессора на Jupiter. Использована только как контекст, не является частью описанного эксперимента и не противоречит ему.

## ❓ FAQ

### Q: What is the essence of the new method for verifying quantum advantage?
**A:** The scientists proposed an experimental “game” based on a complement sampling task: all answer options are divided into two equal groups A and B, and the goal is to obtain a random element from group A and return an element from group B. A quantum computer manages this thanks to superposition, while classical machines cannot.

### Q: What equipment was used for the experiment?
**A:** The algorithm was tested on the Quantinuum H2 trapped-ion quantum computer, applying thousands of circuits and scaling the experiment up to 55 qubits; in a test with 37-bit strings the result was statistically unreachable for classical algorithms.

### Q: Is further development of this experiment planned?
**A:** Yes, the authors intend to separate the answer-selection and answer-analysis systems onto two distinct quantum computers connected by a genuine quantum communication channel.