Dequantizing the Quantum Singular Value Transform

on YouTube ↗47m

" summary

Introduces GLH (guided local Hamiltonian) and claims two sharp results: with a sampling-access representation of a guiding state, sparse Hamiltonians and constant precision let a classical polynomial-time algorithm dequantize the QSVT (uses randomized sampling like Tang, sparse matrix queries, Chebyshev-style polynomial filtering and inner-product estimation; epsilon ≤ 1/8, constant overlap delta suffices). Conversely, giving a simple semi-classical subset state and requiring 1/poly precision makes GLH BQP‑hard via Feynman–Kitaev history states, idling tricks and Anderson-style gadgets, so the classical fix fails at chemist precision.

AI-written summary · about

" chapters (5)

1. 0:00Start
2. 1:32Guiding questions
3. 17:02Punchline
4. 34:49Quantum PCP conjecture
5. 38:40Tool 2: Block encoding à la Ambainis

" related talks

• 01h 36mAlgorithms for Algebraic Lattices: Classical and QuantumLéo Ducas · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 31mDemonstrating an Unconditional Separation Between Quantum and Classical Information ResourcesWilliam Kretchmer · Quantum Industry Day 2025
• 58mQuantum 2Mark Zhandry · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 04mQuantum 1Mark Zhandry · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 48mCommitments to Quantum StatesFermi Ma · Minimal Complexity Assumptions for Cryptography 2023
• 01h 13mQuantum Money based on LatticesPeter W. Shor · Lattices: New Cryptographic Capabilities 2020
• 33mSolving SVP and CVP in 2^n time with Discrete Gaussian Sampling – Noah Stephens-DavidowitzNoah Stephens-Davidowitz · The Mathematics of Modern Cryptography
• 01h 26mQuantum FHEUrmila Mahadev · Lattices: New Cryptographic Capabilities 2020