Quantum Wave in Computing Reunion 2021
2021-07-15
-- online --
who it's for
theoretical quantum computer scientists, quantum algorithm designers, quantum complexity researchers, quantum cryptographers, quantum machine learning researchers, quantum error correction designers, quantum hardware experimentalists
topics
classical verification of quantum advantage; adiabatic quantum computation without sign problem; Hamiltonian complexity in thermodynamic limit; learning local Hamiltonians from Gibbs states; graph-based quantum speedups; limits of quantum convex optimization; quantum signal processing optimization; interactive synthesis of quantum states; one-way functions to secure quantum OT; hardness of noisy random quantum circuits; quantum pseudorandomness from spectral gaps; twisted product constructions for LDPC quantum codes
| title | author | length |
|---|---|---|
| Classical Verification of Quantum Computational Advantage | Greg Meyer | 45m |
A concrete interactive protocol shows a classical verifier can certify quantum advantage by having the prover commit to a TCF superposition, condensing the two… | ||
| (Sub)Exponential Advantage of Adiabatic Quantum Computation With No Sign Problem | András Pál Gilyén | 37m |
Constructs sparse, sign-problem-free Hamiltonians (adjacency matrices of large graphs) with a straight linear interpolation and inverse-polynomial spectral gap… | ||
| Hamiltonian Complexity in the Thermodynamic Limit | Sandy Irani | 45m |
Proves a fixed, translationally invariant 2D Hamiltonian whose thermodynamic-limit ground energy density encodes an entire function: each bit of the infinite… | ||
| Optimal Learning of Quantum Hamiltonians From High-Temperature Gibbs States | Ewin Tang | 44m |
Proves optimal sample complexity for learning L‑local n‑qubit Hamiltonian coefficients from high‑temperature Gibbs states (beta below a constant): sample count… | ||
| Symmetries, Graph Properties, and Quantum Speedups | Andrew M. Childs | 46m |
Shows three concrete claims: graphs described by an adjacency matrix admit at most a 6th power bound (more generally a 3K power for K‑uniform hypergraph… | ||
| No Quantum Speedup Over Gradient Descent for Non-Smooth Convex Optimization | Robin Kothari | 44m |
Claim: in the standard first-order black-box model for constrained non-smooth convex optimization, quantum algorithms need the same Theta((GR/ε)^2) oracle… | ||
| Optimization Based Approach for Quantum Signal Processing and Its Energy Landscape | Lin Lin | 47m |
An optimization-based algorithm reliably finds QSP phase factors at standard double precision for degrees beyond 10,000, outperforming algebraic root-finding… | ||
| Interactive Proofs for Synthesizing Quantum States and Unitaries | Henry Yuen | 45m |
Proves that space-uniform families of n‑qubit states admit interactive synthesis protocols, i.e. state PSPACE ⊆ state QIP, with perfect completeness and the… | ||
| One-Way Functions Imply Secure Computation in a Quantum World | Andrea Coladangelo | 41m |
Claims that one-way functions imply OT (and thus secure multi-party quantum computation) via a concrete quantum protocol, using BB84-style exchanges plus a new… | ||
| Quantum Learning Algorithms Imply Circuit Lower Bounds | Alex B. Grilo | 46m |
Claim: nontrivial quantum learners for a circuit class C (produce a quantum hypothesis with error 1/2−γ in time roughly γ^2·2^n/n) imply uniform circuit lower… | ||
| Noise vs Imprecision in the Hardness of Random Quantum Circuits | Bill Fefferman | 45m |
Proves average‑to‑worst‑case hardness for random circuit output probabilities using Feynman path integrals, polynomial structure and a Stockmeyer reduction… | ||
| Quantum Pseudo-Randomness From Domain Walls and Spectral Gaps | Nicholas Hunter-Jones | 45m |
Local brickwork random circuits on n qubits with local dimension q form approximate unitary k designs in depth scaling linear in n and k when q is large, with… | ||
| Device-Independent Protocols From Computational Assumptions | Tony Metger | 44m |
Proposes device-independent QKD that drops the usual no-communication assumption by instead assuming the untrusted device is computationally bounded and cannot… | ||
| On the NLTS Conjecture | Chinmay Nirkhe | 45m |
Posits the NLTS conjecture and proves a first unconditional circuit-depth lower bound for all low-energy states of certain LDPC stabilizer Hamiltonians by… | ||
| Strongly Universal Hamiltonian Simulators | Leo Zhou | 43m |
Claim: any Hamiltonian whose time evolution a polynomial-size quantum circuit approximates gets encoded as the low-energy sector of a simple simulator with… | ||
| Quantum Garbled Circuits | Zvika Brakerski | 49m |
Defines quantum randomized encoding (decomposable, gate-by-gate) and constructs random Clifford + classical side information encodings that decode to the… | ||
| Quantum Algorithms for Escaping from Saddle Points | Tongyang Li | 48m |
Claims a hybrid algorithm that uses quantum simulation of the Schrödinger equation to replace classical random perturbations and escapes saddle points with the… | ||
| Quantum Generative Training Using Rényi Divergences | Nathan Wiebe | 40m |
Method claims efficient gradient-based training of quantum generative models by minimizing the max Rényi divergence (α=2) so the gradient is differentiable… | ||
| Quantum Pseudorandomness and Classical Complexity | William Kretschmer | 37m |
Constructs a simple quantum oracle where BQP = QMA relative to a quantum oracle while simultaneously pseudorandom quantum states (PRSs) exist relative to that… | ||
| Provably Efficient Machine Learning for Quantum Many-Body Problems | Hsin-Yuan Huang | 43m |
Proves that classical ML using classical shadow (randomized Pauli) can learn ground states and phases for smooth families of geometrically local Hamiltonians… | ||
| A Rigorous and Robust Quantum Speed-up in Supervised Machine Learning | Yunchao Liu | 29m |
Proves an end-to-end quantum speedup for supervised classification by designing a kernel that is classically hard but solvable by quantum kernel estimation… | ||
| Exponential Separations Between Learning With and Without Quantum Memory | Jordan Cotler | 39m |
Claims an exponential gap between protocols that can store quantum states and those limited to classical memory, supported by a new learning tree framework and… | ||
| Entanglement Spread in Communication Complexity and Many-Body Physics | Aram Harrow | 45m |
Defines entanglement spread as the operational width of a Schmidt-weight distribution and proves it both upper- and lower-bounds the qubit communication needed… | ||
| Linear Growth of Quantum Circuit Complexity | Jonas Haferkamp | 44m |
Shows a rigorous linear lower bound on exact quantum circuit complexity for Haar-random two‑qubit gates arranged in local architectures, holding with… | ||
| Improved Upper Bounds on the Stabilizer Rank of Magic States | David Gosset | 46m |
Proves a smaller exponential upper bound on the exact stabilizer rank of M magic states by building large code states from small ones rather than blocking… | ||
| What the Foundations of Quantum Computer Science Teach Us About Chemistry | Jarrod R. McClean | 48m |
Argues that real-world data dramatically changes computational hardness: starting from an easy Hartree‑Fock circuit and adding interaction layers produces… | ||
| Twisted Product Constructions for LDPC Quantum Codes | Nikolas Breuckmann | 44m |
Three product constructions use twists in fiber bundles, lifted products over group algebras, and balanced products with symmetry reduction to build LDPC CSS… | ||
| Electronic Structure in a Fixed Basis Is QMA-Complete | Bryan O’Gorman | 31m |
Determines that ground-state energy in a fixed single-particle basis with fixed particle number and inverse-polynomial precision is QMA-complete, and that… | ||
| nothing matches | ||