6 papers
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…
Efficient Quantum Fourier Transforms For Semisimple Algebras
Ben Foxman, Barak Nehoran, Yongshan Ding
The quantum Fourier transform (QFT) is a fundamental primitive in quantum computation and quantum information. In this work, we generalize the QFT for finite groups to a QFT for fi…
A General Quantum Duality for Representations of Groups with Applications to Quantum Money, Lightning, and Fire
John Bostanci, Barak Nehoran, Mark Zhandry
Aaronson, Atia, and Susskind (2020) established that efficiently mapping between quantum states and is computationally equivalent to distinguishing their…
Oracle Separation Between Quantum Commitments and Quantum One-wayness
John Bostanci, Boyang Chen, Barak Nehoran
We show that there exists an oracle relative to which quantum commitments exist but no (efficiently verifiable) one-way state generators exist. Both have been widely considered can…
A Computational Separation Between Quantum No-cloning and No-telegraphing
Barak Nehoran, Mark Zhandry
Two of the fundamental no-go theorems of quantum information are the no-cloning theorem (that it is impossible to make copies of general quantum states) and the no-teleportation th…
Unconditionally Secure Commitments with Quantum Auxiliary Inputs
Tomoyuki Morimae, Barak Nehoran, Takashi Yamakawa
We show the following unconditional results on quantum commitments in two related yet different models: 1. We revisit the notion of quantum auxiliary-input commitments introduced b…