#exponentiallyhard

[govindhtech]

Quantum USC & IBM Certified For Modified Simon’s Problem

USC researchers demonstrate exponential quantum speedup, enabling quantum advantage.

USC researchers led by Dr. Daniel Lidar used IBM quantum computers to verify an exponential algorithmic speedup for a modified Simon's problem in a groundbreaking study. This Physical Review X study is one of the first to show quantum scaling speedup without using untested notions about classical method constraints. By executing circuits on noisy quantum hardware like two 127-qubit IBM Quantum Eagle processors (ibm_brisbane and ibm_sherbrooke), the team showed that quantum speedup scaled exponentially with issue size.

A Quantum Computing “Holy Grail” Found

The exponential scaling speedup proof marked a turning point in quantum computing. Dr. Daniel Lidar considers this the “holy grail of quantum computing” since an exponential scaling speedup shows “As variables increase issue size, the quantum-classical performance gap grows, to the advantage of the quantum side.” Quantum devices had only showed polynomial speedup till now. This study proves current quantum computers can gain quantum advantage without conjecture.

A quantum guessing game for Simon's Problem

The study examined a “oracle-based game,” a modified version of Simon’s problem. In this game, players must anticipate a hidden bitstring (b) known only to an oracle (a black box) with the fewest queries possible. Lidar's team limited the bitstring's Hamming weight—its number of “1s”—to reduce circuit complexity.

How modified Simon's problem works:

A secret bitstring b with a fixed Hamming weight w is chosen. A mystery function f is specified to equal f(y) only if x = y or x = y + b. All outputs share exactly two inputs, offset by the hidden bitstring b. Players request f(x) from the oracle. Although classical computers query sequentially, quantum computers can query in superposition, allowing complex linear combinations of states until measured. Based on bit count, classical computers find this hidden bitstring “exponentially hard” to find. Daniel Simon showed in 1994 that a flawless, noiseless quantum computer could solve this problem in a few queries, giving it an exponential advantage over traditional methods. Simon's problem is a "stepping-stone to Shor's period-finding problem," which is not oracle-based and has profound implications, although having no known real-world applicability. Both topics are abelian hidden subgroup problems.

Recovering Near-Term Quantum Computer Performance Lidar's team developed many key approaches to realise exponential speedup with today's "pre-fault-tolerant quantum hardware," including:

Circuit Optimisation: To reduce noise, researchers reduced quantum logic processes to reduce circuit depth. They largely used Qiskit's ability to shallowen Simon's issue circuit. Dynamical Decoupling: Essential for noise suppression. To reverse dephasing noise caused by idle qubits interacting with the environment or other qubits (crosstalk), microwave pulse sequences are added. Dynamic decoupling enhanced quantum results, bringing the scaling curve closer to noiseless. Error Mitigation: After dynamical decoupling, they used methods to find and fix measurement mistakes. The researchers proved that a quantum player may win exponentially faster than a classical one.

Noticed Speedup and Implications

Researchers used Number of Oracle Queries to Solution to measure speedup. A traditional player typically requires Ω(nw/2) enquiries, indicating exponential scaling. Ideal quantum players only need O(w logn) queries. The oracle model exhibited a quantum speedup, and the quantum processor had a shallower slope that matched the ideal result, showing exponential increase over classical scaling.

Problem sizes accelerated to 58 qubits for Hamming weights up to w = 7. Modern quantum computers' increased circuit depth and intrinsic noise made the quantum method less effective for Hamming weights of w = 8 and w = 9. According to the study, “today’s quantum computers firmly lie on the side of quantum advantage, without any conjectures,” giving other practical outcomes “more solid footing.”

This paper emphasises the importance of algorithm development in delivering near-term quantum technology benefits, motivating the quantum community to undertake more experiments and expedite quantum advantage.