The Hidden Subgroup Problem for Infinite Groups

on YouTube ↗40m

" summary

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 any rank, extending Shor–Kitaev. Algorithm uses Gaussian‑prepared wide states and a large‑Q Fourier sampling, then classical postprocessing: LLL lattice reduction, greedy Cauchy‑Binet submatrix selection, continued‑fraction rational recovery and Smith normal form to reduce to a Shor–Kitaev step. A single noisy Fourier sample often suffices with high probability; parameter scaling and sample‑tradeoffs remain open.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:38The hidden subgroup problem
3. 3:21The Shor-Kitaev algorithm
4. 5:09HSP when G is finite
5. 10:17New negative results when G is infinite
6. 12:13A new positive result
7. 17:21The HSP algorithm in z
8. 18:38Fourier measurement and dual samples
9. 25:24Solving for from random samples
10. 28:23Lifting a dense orbit to a lattice
11. 29:27Denoising the data
12. 34:12The last step
13. 34:59Open problems

" related talks

• 01h 36mAlgorithms for Algebraic Lattices: Classical and QuantumLéo Ducas · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 04mQuantum 1Mark Zhandry · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 57mAlgorithms for Lattice Problems, in PracticeElena Kirshanova, Pierre-Alain Fouque · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 28mPost-Quantum ManifestoPhilippe Lamontagne · NorthSec 2019
• 44mLattices with SymmetryAlice Silverberg · The Mathematics of Modern Cryptography
• 01h 04mUsing Lattices for CryptanalysisNadia Heninger · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 01h 06mAlgorithms for the k-List ProblemsElena Kirshanova · Lattices: Geometry, Algorithms and Hardness 2020
• 01h 07mSomething about new average-case hard problems?Tselil Schramm · Obfuscation