Speaker
Description
While most quantum algorithms either offer sampling advantages with zero fault tolerance or computational advantages with universal fault tolerance, early fault-tolerant quantum devices occupy an intermediate regime in which substantial but not fully universal error-corrected computation is possible. This contrast motivates the question of whether quantum-classical separations can be achieved with substantially sub-universal fault-tolerance. We propose a family of such problems based on sequence learning: two long sequences are respectively given to an encoder and a decoder, and the encoder may pass a short representation of its sequence to the decoder. The decoder must then learn to compute a function of the two sequences. We give a quantum algorithm for sequence learning, indexed by a parameter $k$, such that all training can be done efficiently completely classically, and the entire learned circuit uses only a single $k$-qubit phase gate (plus initialization and a final $X$-basis measurement).
Next we construct an explicit distributional problem based on polynomial evaluation, and prove that our quantum algorithm succeeds perfectly using $n$ qubits passed from encoder to decoder. On the other hand, we prove that every classical linear encoder requires $\Omega(n^k)$ bits to achieve constant advantage over random guessing, and conjecture that the same lower bound holds for all classical encoders, giving an $n^k$ memory separation realizable with a single reliable gate. In practice, we find numerically that the quantum model often outperforms natural classical counterparts even on much simpler problems, suggesting that this model may be of more generic utility beyond carefully constructed tasks.
| Topic | Hybrid quantum-classical approaches for learning and optimization |
|---|---|
| Additional Topic | Quantum variational circuits and their applications |