REVIEW 5 cited by
Revisiting dequantization and quantum advantage in learning tasks
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
It has been shown that the apparent advantage of some quantum machine learning algorithms may be efficiently replicated using classical algorithms with suitable data access -- a process known as dequantization. Existing works on dequantization compare quantum algorithms which take copies of an n-qubit quantum state $|x\rangle = \sum_{i} x_i |i\rangle$ as input to classical algorithms which have sample and query (SQ) access to the vector $x$. In this note, we prove that classical algorithms with SQ access can accomplish some learning tasks exponentially faster than quantum algorithms with quantum state inputs. Because classical algorithms are a subset of quantum algorithms, this demonstrates that SQ access can sometimes be significantly more powerful than quantum state inputs. Our findings suggest that the absence of exponential quantum advantage in some learning tasks may be due to SQ access being too powerful relative to quantum state inputs. If we compare quantum algorithms with quantum state inputs to classical algorithms with access to measurement data on quantum states, the landscape of quantum advantage can be dramatically different. We remark that when the quantum states are constructed from exponential-size classical data, comparing SQ access and quantum state inputs is appropriate since both require exponential time to prepare.
Forward citations
Cited by 5 Pith papers
-
High-rate qLDPC processors
Non-abelian "mitten" qLDPC codes achieve 20% encoding rate with distances 10-24 on 150-975 qubits, and simulations indicate fault-tolerant processors sustaining ~10^10 logical operations at 0.1% physical error rate.
-
Optimal complex conjugation of unknown isometry channels
The optimal n-use fidelity for complex conjugating an unknown isometry C^d→C^D is derived in closed form, with parallel protocols proven optimal among all general quantum superchannels.
-
Quantum Computer Benchmarking: An Explorative Systematic Literature Review
A systematic review of 329 quantum benchmarking studies yields a stack-aligned taxonomy and definitions for hardware-, software-, and application-focused benchmarks.
-
Quantum reinforcement learning of classical rare dynamics: Enhancement by intrinsic Fourier features
Quantum reinforcement learning agents with one- and two-qubit parameterized circuits learn to generate random walk bridges in a toy rare-event task and can match or beat small neural-network agents with fewer parameters.
-
A brief history of quantum vs classical computational advantage
A single-author review of all quantum computational advantage claims to date, their classical refutations, and the progress of quantum error correction.
Discussion (0). Continue with ORCID to comment.