4 papers · 1 filter
A measurement-driven quantum algorithm for SAT: Performance guarantees via spectral gaps and measurement parallelization
Franz J. Schreiber, Maximilian J. Kramer, Alexander Nietner +1
The Boolean satisfiability problem (SAT) is of central importance in both theory and practice. Yet, most provable guarantees for quantum algorithms rely exclusively on Grover-type…
On the average-case complexity of learning output distributions of quantum circuits
Alexander Nietner, Marios Ioannou, Ryan Sweke +4
In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely…
Interactive proofs for verifying (quantum) learning and testing
Matthias C. Caro, Jens Eisert, Marcel Hinsche +3
We consider the problem of testing and learning from data in the presence of resource constraints, such as limited memory or weak data access, which place limitations on the effici…
Free Fermion Distributions Are Hard to Learn
Alexander Nietner
Free fermions are some of the best studied quantum systems. However, little is known about the complexity of learning free-fermion distributions. In this work we establish the hard…