370 citations · 549 across the 19 of their papers we have counts for
27 papers
On the pseudorandomness of simple quantum processes
Jesko Dujmovic, Jonas Haferkamp, Alexander Poremba
Can simple processes appear highly complex? Gowers (Comb. Prob. Comp. '96) conjectured that repeatedly composing local random reversible operations can yield global permutations th…
Rounding Almost Commuting Hamiltonians
Islam Faisal, Anand Natarajan, Alexander Poremba
Commuting Hamiltonians lie at the boundary between classical constraint satisfaction and quantum many-body physics, exhibiting rich quantum structure while remaining more tractable…
Post-Quantum Cryptography from Quantum Stabilizer Decoding
Jonathan Z. Lu, Alexander Poremba, Yihui Quek +1
Post-quantum cryptography currently rests on a small number of hardness assumptions, posing significant risks should any one of them be compromised. This vulnerability motivates th…
Hamiltonian Decoded Quantum Interferometry
Alexander Schmidhuber, Jonathan Z. Lu, Noah Shutty +3
We introduce Hamiltonian Decoded Quantum Interferometry (HDQI), a quantum algorithm that utilizes coherent Bell measurements and the symplectic representation of the Pauli group to…
Average-Case Complexity of Quantum Stabilizer Decoding
Andrey Boris Khesin, Jonathan Z. Lu, Alexander Poremba +2
Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all…
Cloning Games, Black Holes and Cryptography
Alexander Poremba, Seyoon Ragavan, Vinod Vaikuntanathan
In this work, we introduce a new toolkit for analyzing cloning games, a notion that captures stronger and more quantitative versions of the celebrated quantum no-cloning theorem. T…
(Quantum) Indifferentiability and Pre-Computation
Joseph Carolan, Alexander Poremba, Mark Zhandry
Indifferentiability is a popular cryptographic paradigm for analyzing the security of ideal objects -- both in a classical as well as in a quantum world. It is typically stated in…
The Learning Stabilizers with Noise problem
Alexander Poremba, Yihui Quek, Peter Shor
Random classical codes have good error correcting properties, and yet they are notoriously hard to decode in practice. Despite many decades of extensive study, the fastest known al…
Revocable Encryption, Programs, and More: The Case of Multi-Copy Security
Prabhanjan Ananth, Saachi Mutreja, Alexander Poremba
Fundamental principles of quantum mechanics have inspired many new research directions, particularly in quantum cryptography. One such principle is quantum no-cloning which has led…
Efficient Quantum Pseudorandomness from Hamiltonian Phase States
John Bostanci, Jonas Haferkamp, Dominik Hangleiter +1
Quantum pseudorandomness has found applications in many areas of quantum information, ranging from entanglement theory, to models of scrambling phenomena in chaotic quantum systems…
Simple constructions of linear-depth t-designs and pseudorandom unitaries
Tony Metger, Alexander Poremba, Makrand Sinha +1
Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties, but cannot be implemented efficiently. This has motivated a long line of resear…
Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations
Joseph Carolan, Alexander Poremba
Sponge hashing is a widely used class of cryptographic hash algorithms which underlies the current international hash function standard SHA-3. In a nutshell, a sponge function take…
Pseudorandom unitaries with non-adaptive security
Tony Metger, Alexander Poremba, Makrand Sinha +1
Pseudorandom unitaries (PRUs) are ensembles of efficiently implementable unitary operators that cannot be distinguished from Haar random unitaries by any quantum polynomial-time al…
Revocable Quantum Digital Signatures
Tomoyuki Morimae, Alexander Poremba, Takashi Yamakawa
We study digital signatures with revocation capabilities and show two results. First, we define and construct digital signatures with revocable signing keys from the LWE assumption…
On the Two-sided Permutation Inversion Problem
Gorjan Alagic, Chen Bai, Alexander Poremba +1
In the permutation inversion problem, the task is to find the preimage of some challenge value, given oracle access to the permutation. This is a fundamental problem in query compl…
Unitary Complexity and the Uhlmann Transformation Problem
John Bostanci, Yuval Efron, Tony Metger +3
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot…
Weakening Assumptions for Publicly-Verifiable Deletion
James Bartusek, Dakshita Khurana, Giulio Malavolta +2
We develop a simple compiler that generically adds publicly-verifiable deletion to a variety of cryptosystems. Our compiler only makes use of one-way functions (or one-way state ge…
Publicly-Verifiable Deletion via Target-Collapsing Functions
James Bartusek, Dakshita Khurana, Alexander Poremba
We build quantum cryptosystems that support publicly-verifiable deletion from standard cryptographic assumptions. We introduce target-collapsing as a weakening of collapsing for ha…
Revocable Cryptography from Learning with Errors
Prabhanjan Ananth, Alexander Poremba, Vinod Vaikuntanathan
Quantum cryptography leverages many unique features of quantum information in order to construct cryptographic primitives that are oftentimes impossible classically. In this work,…
Improved Quantum Algorithms for Fidelity Estimation
András Gilyén, Alexander Poremba
Fidelity is a fundamental measure for the closeness of two quantum states, which is important both from a theoretical and a practical point of view. Yet, in general, it is difficul…
Quantum Proofs of Deletion for Learning with Errors
Alexander Poremba
Quantum information has the property that measurement is an inherently destructive process. This feature is most apparent in the principle of complementarity, which states that mut…
Quantum cryptography with classical communication: parallel remote state preparation for copy-protection, verification, and more
Alexandru Gheorghiu, Tony Metger, Alexander Poremba
Quantum mechanical effects have enabled the construction of cryptographic primitives that are impossible classically. For example, quantum copy-protection allows for a program to b…
Quantum copy-protection of compute-and-compare programs in the quantum random oracle model
Andrea Coladangelo, Christian Majenz, Alexander Poremba
Copy-protection allows a software distributor to encode a program in such a way that it can be evaluated on any input, yet it cannot be "pirated" - a notion that is impossible to a…
Variational Quantum Fidelity Estimation
M. Cerezo, Alexander Poremba, Lukasz Cincio +1
Computing quantum state fidelity will be important to verify and characterize states prepared on a quantum computer. In this work, we propose novel lower and upper bounds for the f…