120 citations · 298 across the 11 of their papers we have counts for
11 papers
Parallel Spooky Pebbling Makes Regev Factoring More Practical
Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Katherine Van Kirk
Pebble games, an abstraction from classical reversible computing, have found use in the design of quantum circuits for inherently sequential tasks. Gidney showed that allowing Hada…
A log-depth in-place quantum Fourier transform that rarely needs ancillas
Gregory D. Kahanamoku-Meyer, John Blue, Thiago Bergamaschi +2
When designing quantum circuits for a given unitary, it can be much cheaper to achieve a good approximation on most inputs than on all inputs. In this work we formalize this idea,…
The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth
Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan +1
We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA int…
Fast quantum integer multiplication with zero ancillas
Gregory D. Kahanamoku-Meyer, Norman Y. Yao
The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime qu…
Simple Tests of Quantumness Also Certify Qubits
Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer +2
A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain templ…
Interactive Protocols for Classically-Verifiable Quantum Advantage
Daiwei Zhu, Gregory D. Kahanamoku-Meyer, Laura Lewis +15
Achieving quantum computational advantage requires solving a classically intractable problem on a quantum device. Natural proposals rely upon the intrinsic hardness of classically…
Classically-Verifiable Quantum Advantage from a Computational Bell Test
Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani +1
We propose and analyze a novel interactive protocol for demonstrating quantum computational advantage, which is efficiently classically verifiable. Our protocol relies upon the cry…
Enhancing Scalability of a Matrix-Free Eigensolver for Studying Many-Body Localization
Roel Van Beeumen, Khaled Z. Ibrahim, Gregory D. Kahanamoku-Meyer +2
In [Van Beeumen, et. al, HPC Asia 2020, https://www.doi.org/10.1145/3368474.3368497] a scalable and matrix-free eigensolver was proposed for studying the many-body localization (MB…
Many-Body Chaos in the Sachdev-Ye-Kitaev Model
Bryce Kobrin, Zhenbin Yang, Gregory D. Kahanamoku-Meyer +4
Many-body chaos has emerged as a powerful framework for understanding thermalization in strongly interacting quantum systems. While recent analytic advances have sharpened our intu…
Forging quantum data: classically defeating an IQP-based quantum test
Gregory D. Kahanamoku-Meyer
Recently, quantum computing experiments have for the first time exceeded the capability of classical computers to perform certain computations -- a milestone termed "quantum comput…
Long-Range Prethermal Phases of Nonequilibrium Matter
Francisco Machado, Dominic V. Else, Gregory D. Kahanamoku-Meyer +2
We prove the existence of non-equilibrium phases of matter in the prethermal regime of periodically-driven, long-range interacting systems, with power-law exponent , where $d…