Quantum and Lattices Joint Reunion Workshop
2022-06-13..2022-06-16
Berkeley, United States
who it's for
quantum computing researchers, quantum cryptographers, lattice cryptographers, theoretical computer scientists, quantum algorithm designers, experimental quantum physicists, postquantum protocol implementers
topics
quantum advantage experiments; random-circuit sampling verification; dequantizing quantum singular value transform; subspace state preparation; quantum benchmarking and classical shadows; quantum rewinding techniques; hidden subgroup problem on Z^d; lattice-based learning with errors (LWE); lattice-based zero-knowledge proofs; broadcast encryption from evasive LWE; witness encryption from lattice techniques; single-server private information retrieval
| title | author | length |
|---|---|---|
| Recent Progress in Quantum Advantage | Scott Aaronson | 01h 09m |
Argues that useful exponential quantum advantage needs three things at once: NISQ-able hardware, a clear classical hardness gap, and an efficiently verifiable… | ||
| Quantum Advantage Without Structure | Mark Zhandry | 01h 06m |
Proves, relative to a random oracle, an NP search in BQP not BPP by encoding witnesses as codewords whose symbols each pass an oracleed validity test… | ||
| The Hidden Subgroup Problem for Infinite Groups | Greg Kuperberg | 40m |
Shows HSP on Q is NP‑hard relative to BQP or with a factoring oracle, and gives a polynomial‑time quantum algorithm for G = Z^d when the hidden subgroup has… | ||
| Dequantizing the Quantum Singular Value Transform | Sev Gharibian | 47m |
Introduces GLH (guided local Hamiltonian) and claims two sharp results: with a sampling-access representation of a guiding state, sparse Hamiltonians and… | ||
| Quantum Linear Algebra Using Subspace States | Anupam Prakash | 48m |
Claims an implemented circuit family that prepares subspace states and yields a polynomial determinantal-sampling speedup: a quantum algorithm using Clifford… | ||
| Learning from Quantum Experiments | Robert Huang | 01h 10m |
Recent results show a practical protocol that uses random Clifford sampling and simple postprocessing (median‑of‑means on stored classical shadows) to predict… | ||
| New Quantum Cryptographic Primitives I | Mark Zhandry | 01h 05m |
Survey of concrete proposals for mini-scheme public-key quantum money: banknotes are subspace states verified by membership tests and a Fourier-check, with… | ||
| New Quantum Cryptographic Primitives II | Mark Zhandry | 01h 08m |
Quantum copy protection faces clear boundaries and partial constructions: learnable functions are impossible to protect and Aaronson’s 2009 quantum-oracle… | ||
| Quantum Benchmarking | Yunchao Liu | 50m |
Classifies exactly which parameters of gate noise are learnable for Clifford operations using a pattern transfer graph, shows a CNOT has 13 learnable, 2… | ||
| Quantum Rewinding Tutorial, Part 1: Motivation and Early Rewinding Techniques | Alex Lombardi, Fermi Ma | 01h 12m |
Proves that Blum’s Hamiltonian-cycle protocol achieves post-quantum soundness and zero knowledge assuming collapse-binding commitments (instantiable from LWE… | ||
| Quantum Rewinding Tutorial, Part 2: How to Run a Quantum Attacker Many Times | Alex Lombardi, Fermi Ma | 01h 11m |
Shows a concrete alternating projectors procedure that repairs a measured quantum prover by alternating the challenge projector Pi_R with a projector… | ||
| Quantum Rewinding Tutorial, Part 3: Zero Knowledge Simulation Beyond Watrous | Alex Lombardi, Fermi Ma | 01h 14m |
Claims a constructive simulator that achieves guaranteed extraction of witnesses for three‑message proofs against quantum verifiers and then preserves the… | ||
| Hardness of the Shortest Vector Problem: A Simplified Proof and a Survey | Huck Bennett | 01h 06m |
Claims a simpler randomized NP‑hardness reduction for GAP‑SVP that builds Reed–Solomon parity‑check lattices (prime Q, K ≈ Q^ε), shows L1 minimum distance ≈ 2K… | ||
| Bourgain’s Slicing Problem and KLS Isoperimetry up to Polylog | Bo’az Klartag | 59m |
Claim: Bourgain's slicing constant and KLS isoperimetric constant are bounded up to polylog factors — specifically L_n ≤ (log n)^4, σ_n ≤ (log n)^4 and ψ_n ≤… | ||
| Some Recent Results Showing that Lattice Problems Are (sort of) Equivalent in All Norms | Noah Stephens-Davidowitz | 59m |
Shows that for large constant approximation factors lattice problems in any Lp norm run in essentially the same time as in L2, giving a 2^{0.8n} algorithm for… | ||
| Doubly Efficient Private Information Retrieval | Elette Boyle | 01h 04m |
Single‑server PIR that makes both client and server efficient uses a one‑time preprocessing and a new hardness conjecture: encode the n‑bit database via a… | ||
| Single-Server Private Information Retrieval with Sublinear Amortized Time | Alexandra Henzinger | 43m |
Gives concrete constructions: under DDH/QR/DCR/LWE a single-server PIR achieves n^{3/4} amortized server time with client storage n^{3/4} and supports ~n^{1/4}… | ||
| Optimal Broadcast Encryption and More from Evasive LWE | Hoeteck Wee | 46m |
New construction gives ciphertext-policy ABE and optimal broadcast encryption from a new lattice hypothesis called evasive LWE plus standard LWE… | ||
| Candidate Witness Encryption from Lattice Techniques | Rotem Tsabary | 46m |
Proposes a lattice-based candidate witness encryption built from GGH15 encodings that assigns an LWE secret to each edge and adds per-bit consistency memory… | ||
| Lattice-based Zero-knowledge Proofs | Vadim Lyubashevsky | 01h 06m |
A practical toolbox for lattice-based zero-knowledge condenses range proofs, commitments and algebraic tricks to get from megabyte-scale proofs down to 10–20… | ||
| Batch Arguments for NP and SNARGs for P from LWE | Abhishek Jain | 01h 07m |
Claims a construction of SNARKs for P and for Batch NP using LWE by combining LWE-based correlation-intractable hash functions with SSV commitments that… | ||
| Continuous LWE is as Hard as LWE | Neekon Vafa | 56m |
Claim: continuous LWE (CLWE) is as hard as standard LWE via a classical reduction. Proof path: use LWE leakage-resilience to convert to binary sparse secrets… | ||
| nothing matches | ||