1 citations · 1 across the 5 of their papers we have counts for
6 papers
Lower Bounds for Preprocessing Attacks on Quantum Cryptography
Fangqi Dong, Alex Lombardi
We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a -query adversary with qubits of…
Explicit Separations for One-Query Unitary Synthesis
Fangqi Dong, Alex Lombardi, Fermi Ma
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every -qubit unitary is computable by efficient quantum circuits relative to some classical oracle…
Quantum Lazy Sampling and Path Recording for Any Group
Ben Foxman, Alex Lombardi, Fermi Ma +2
A central challenge in quantum algorithms and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, permutation, or unita…
Strong random unitaries and fast scrambling
Thomas Schuster, Fermi Ma, Alex Lombardi +2
Understanding how fast physical systems can resemble Haar-random unitaries is a fundamental question in physics. Many experiments of interest in quantum gravity and many-body physi…
A one-query lower bound for unitary synthesis and breaking quantum cryptography
Alex Lombardi, Fermi Ma, John Wright
The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any -qubit unitary can be implemented by an efficient quantum algorithm augmented with an oracle tha…
Post-Quantum Zero Knowledge, Revisited (or: How to Do Quantum Rewinding Undetectably)
Alex Lombardi, Fermi Ma, Nicholas Spooner
A major difficulty in quantum rewinding is the fact that measurement is destructive: extracting information from a quantum state irreversibly changes it. This is especially problem…