Source-linked AI summary
Demonstration of quantum advantage in machine learning
D. Ristè, Marcus P. da Silva, Colm A. Ryan, Andrew W. Cross, John A. Smolin, Jay M. Gambetta, Jerry M. Chow, Blake R. Johnson
TL;DR
The paper analyzes query complexity and error effects in classical and quantum solvers using a shared oracle implementation. It derives threshold-based correctness conditions and query lower bounds, finding that the asymptotic scaling is unchanged by the analyzed selection choice.
Problem
Classical learning with classification noise can require solving an NP-complete disagreement-minimization problem, motivating complexity analysis across error rates.
Method
The study calibrates a five-qubit superconducting setup and compares digital and analog solvers using identical oracle implementations and voltage-threshold digitization.
Results
The derived lower bound on query number has the same asymptotic scaling under the considered selection choices.
Takeaways & Limitations
Query-complexity analysis must account for readout distributions, effective classification errors, and the dependence of outcomes on typical values of s.
Takeaways & Limitations
The analysis assumes s is typical and preserves the same oracle by not compiling the Hadamard gates in the classical and quantum implementations.
Abstract
from arXiv · showhide
The main promise of quantum computing is to efficiently solve certain problems that are prohibitively expensive for a classical computer. Most problems with a proven quantum advantage involve the repeated use of a black box, or oracle, whose structure encodes the solution. One measure of the algorithmic performance is the query complexity, i.e., the scaling of the number of oracle calls needed to find the solution with a given probability. Few-qubit demonstrations of quantum algorithms, such as Deutsch-Jozsa and Grover, have been implemented across diverse physical systems such as nuclear magnetic resonance, trapped ions, optical systems, and superconducting circuits. However, at the small scale, these problems can already be solved classically with a few oracle queries, and the attainable quantum advantage is modest. Here we solve an oracle-based problem, known as learning parity with noise, using a five-qubit superconducting processor. Running classical and quantum algorithms on the same oracle, we observe a large gap in query count in favor of quantum processing. We find that this gap grows by orders of magnitude as a function of the error rates and the problem size. This result demonstrates that, while complex fault-tolerant architectures will be required for universal quantum computing, a quantum advantage already emerges in existing noisy systems
METHODS
The methods implement and compare classical and quantum solvers for noisy parity learning, using calibrated superconducting-qubit measurements and statistical post-processing. They also derive analog-solver thresholds and performance bounds, including the condition that postselection preserves asymptotic scaling.
- Experimental setup: The five-qubit experiment uses calibrated microwave control, readout, multiplexed measurement, and cross-resonance-based gate sequences.CNOT gates are decomposed into cross-resonance operations, with calibration routines applied to single- and two-qubit pulses.
- Solver comparison: The oracle is kept identical for classical and quantum solvers by avoiding compilation differences in the Hadamard gates.The comparison differs in post-oracle processing rather than oracle construction.
- Classical solver: The Bayesian classical solver updates a posterior over keys from analog voltage observations and selects the most probable key.The procedure iterates posterior updates after each query, using the key maximizing p(k).
- Quantum solvers: The analog quantum solver postselects on the ancilla, averages the retained data-qubit voltages, and digitizes them using thresholds optimized for noisy readout distributions.Without postselection, the Q′ solver uses ηA = 0.5 when determining thresholds.
- Performance analysis: The threshold analysis models depolarizing and measurement errors, conditions bounds on typical postselection outcomes, and computes bitwise correctness probabilities.The threshold is constrained between the conditional means, and correctness is evaluated by whether the averaged voltage lies on the proper side.
- Performance bounds: Postselection can improve finite-query bounds, but its asymptotic scaling is unchanged.The analysis derives lower bounds on the number of queries under typical postselection conditions.