Quantum USC & IBM Certified For Modified Simon's Problem

Exponential quantum speedup is demonstrated by USC researchers, opening the door for quantum advantage.

In a ground-breaking study, scientists at the University of Southern California (USC), under the direction of Dr. Daniel Lidar, used IBM quantum computers to verify an exponential algorithmic speedup for a modified version of Simon’s problem. This work, which was published in Physical Review X, is among the first to demonstrate quantum scaling speedup without depending on unproven hypotheses on the limitations of classical approaches. The team demonstrated that the quantum speedup scaled exponentially with the issue size by running circuits on noisy quantum hardware, such as two 127-qubit IBM Quantum Eagle processors (ibm_brisbane and ibm_sherbrooke).

You can also read Ionq Capella Space Acquisition For Quantum Key Distribution

A “Holy Grail” of Quantum Computing Achieved

An important turning point in quantum computing has been reached with the proof of exponential scaling speedup. An exponential scaling speedup indicates “As variables increase issue size, the quantum-classical performance gap grows, to the advantage of the quantum side,” according to Dr. Daniel Lidar, who calls this accomplishment the “holy grail of quantum computing.” Up until now, quantum hardware had only shown relatively moderate forms of speedup, like polynomial. This study provides verifiable proof that modern quantum computers are capable of achieving quantum advantage without speculation.

Decoding Simon’s Problem: A Quantum Guessing Game

A modified version of Simon’s problem, referred to as an “oracle-based game,” was the subject of the study. In this game, participants must use the fewest number of queries feasible to accurately predict a concealed bitstring (b), which is only known to an oracle (a black box). To control circuit complexity, Lidar’s team changed the game by limiting the bitstring’s Hamming weight, that is, the number of “1s” it contains.

Here’s how the modified Simon’s problem works:

A secret bitstring b with a fixed Hamming weight w is chosen.
A mystery function f is defined such that f(x) = f(y) if and only if x = y or x = y + b. This means each output is shared by exactly two inputs, offset by the hidden bitstring b.
Players query the oracle with an input x to get f(x). While classical computers query sequentially, a quantum computer can query in superposition, allowing for complex linear combinations of states until measured.

This buried bitstring is “exponentially hard” to find for classical computers in relation to the number of bits. An perfect, noiseless quantum computer may theoretically solve this problem in a relatively small number of queries, providing an exponential advantage over traditional approaches, as demonstrated by Daniel Simon in 1994. Despite having no known real-world use, Simon’s problem is an important “stepping-stone to Shor’s period-finding problem,” which is not oracle-based and has important ramifications. Both issues are instances of the hidden subgroup problem that is abelian.

You can also read Bifrosts Electronics Secures $2.5M For Quantum Innovation

Extracting Performance from Near-Term Quantum Computers

Lidar’s team created a number of crucial methods to bring the promise of exponential speedup from theory to reality using today’s “pre-fault-tolerant quantum hardware,” including:

Circuit Optimization: The researchers concentrated on minimizing circuit depth by lowering the amount of necessary quantum logic operations in order to avoid noise accumulation. To transform the unsophisticated Simon’s problem circuit into a shallower one, they mostly relied on Qiskit’s pre-existing capability.
Dynamical Decoupling: This was a critical element in suppressing noise. It involves adding microwave pulse sequences to reverse dephasing noise, which occurs when idle qubits interact with the environment or other qubits (crosstalk). Dynamical decoupling significantly improved quantum results, yielding a scaling curve closer to the ideal noiseless quantum result.
Measurement Error Mitigation: After dynamical decoupling, they applied techniques to identify and correct errors introduced during the measurement process.

These efforts allowed the researchers to show that a quantum player could win exponentially faster than any classical one.

Observed Speedup and Future Implications

The researchers measured speedup using a metric called Number of Oracle Queries to Solution (NTS). A classical player needs roughly Ω(n<sup>w/2</sup>) queries on average, representing exponential scaling. In contrast, an ideal quantum player needs only O(w logn) queries. The experiment showed a clear quantum speedup in the oracle model, with a shallower slope for the quantum processor that more closely reflected the ideal result, indicating exponential improvement over classical scaling.

For Hamming weights up to w = 7, they saw the speedup on problem sizes increase to 58 qubits. Due to the increased circuit depth and intrinsic noise in modern quantum computers, the quantum algorithm lost its advantage for Hamming weights of w = 8 and w = 9. However, the study shows that “today’s quantum computers firmly lie on the side of quantum advantage, without any conjectures,” giving other useful, practical results “more solid footing.”

This study emphasizes the importance of algorithm development in achieving benefits from near-term quantum technology, providing the quantum community with new motivation to conduct more experiments and accelerate the path to quantum advantage.

You can also read SandboxAQ AQNav & Acubed For Quantum Magnetic Navigation

Quantum Computing News