This mirrors the classical #CompressedSensing vs. #ShannonNyquist setting: lower bounds for dense objects stay intact, but sparsity in the right dictionary changes the sample/query complexity.
A huge thanks to Stefano Vanerio, @raistolo.bsky.social, and to everyone who discussed this with me. 6/6
In favorable regimes (e.g., m≈N dictionary vectors, K=Õ(1) sparsity, and well-conditioned support), QOMP lowers the query cost of pure-state #quantum tomography from Θ̃(N/ε) to Ō(√N/ε), breaking known tight lower bounds thanks to the sparsity assumptions. 5/n
We prove that under standard dictionary mutual incoherence and well-conditioning assumptions, QOMP recovers the optimal support in polynomial time! 4/n
To overcome this, we introduce #QOMP: a greedy, iterative #quantumalgorithm that applies block-encoded projections to isolate the residual, estimates overlaps, and identifies one dictionary vector per round, using an error-resetting strategy to prevent error propagation across iterations. 3/n
We formalize and study the problem of #QuantumSparseRecovery: given coherent access to a state and a dictionary, reconstruct the state up to ε ℓ error using as few dictionary vectors as possible. We prove the general problem is #NP-hard, showing that efficiency needs structure. 2/n
I’m happy to announce a new #preprint! 🧑💻📝🎉
Quantum states often show up with hidden structure. What if a state is built from just a few elements of a larger, #non-orthogonal, #overcomplete dictionary? Can we exploit that sparsity to beat standard #tomography costs?
🧵⬇️ /n
CC: @mplavala.bsky.social @scinawa.bsky.social
🎉 Our paper “The Generalized Skew Spectrum of Graphs” was accepted to ICML 2025!
We applied deep math - group theory, rep theory & Fourier analysis - to graph ML (no quantum this time!😄)
📍 See you in Vancouver in July!
📄 arxiv.org/abs/2505.23609
#ICML2025 #GraphML #AI #ML
