1 citations · 1 across the 3 of their papers we have counts for
4 papers · 1 filter
Random-Oracle Unitary Synthesis is Impossible
Andrew Huang, Akshar Ramkumar, John Wright
A major open problem in quantum complexity is the question of unitary synthesis---namely, is it possible to efficiently implement any unitary, given the ability to evaluate any cla…
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…
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…
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…