3 papers
quant-ph2026
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…
quant-ph2024
The state hidden subgroup problem and an efficient algorithm for locating unentanglement
Adam Bouland, Tudor Giurgica-Tiron, John Wright
We study a generalization of entanglement testing which we call the "hidden cut problem." Taking as input copies of an -qubit pure state which is product across an unknown bipar…
quant-ph2023
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…