Most of my research questions fall into one of the following categories:
Quantum algorithms and complexity.
Quantum learning theory with a focus on learning from quantum data.
Quantum cryptography and notions of quantum pseudorandomness.
Quantum many-body physics.
You can find a full list of my publications on my google scholar page or on the arXiv.
Selected publications
Random unitaries in extremely low depth, Thomas Schuster, Jonas Haferkamp, Hsin-Yuan (Robert) Huang, long prenary talk at QIP 2025 [arXiv] [Science]
Short description: We prove that random quantum circuits on any geometry, including a 1D line, can form approximate unitary k-designs over n qubits in log(n) depth. Unitary k-designs are probability distributions over the unitary group that appear uniformly (Haar) random to any adversary with access to k copies of a random unitary. Similarly, we construct pseudorandom unitaries in 1D circuits in polylog(n) depth, and in all-to-all-connected circuits in log log(n) depth. That is, randomly drawn unitaries that are indistiguishable from uniformly random unitaries for all computationally bounded adversaries. In all three cases, the depth scaling is optimal and improves exponentially over known results. These shallow quantum circuits, despite creating only short-range entanglement and having low complexity, are indistinguishable from unitaries of exponential complexity. Applications abound and include proving that classical shadows with 1D log-depth Clifford circuits are as powerful as those with deep circuits, demonstrating superpolynomial quantum advantage in learning low-complexity physical systems, and establishing quantum hardness for recognizing phases of matter with topological order.
Incompressibility and spectral gaps of random circuits, Chi-Fang (Anthony) Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, Xinyu (Norah) Tan, plenary talk at QIP 2025 [arXiv][FOCS]
Short description: In this paper we prove that the circuit complexity of a random circuit grows at a linear rate for up to exponentially many random gates. We show this for both, random quantum circuits and random reversible circuits. This is established by proving (near)-optimal spectral gaps for the moment operators of random (quantum) circuits, which in turn implies the convergence of random circuit to t-wise independence (or unitary t-designs) in a depth linear in t.
Efficient quantum pseudorandomness from Hamiltonian phase states, John Bostanci, Jonas Haferkamp, Dominik Hangleiter, Alexander Poremba [arXiv]
Short description: In this work, we seek to decouple quantum pseudorandomness from classical cryptography for practical applications. We introduce a quantum hardness assumption called the Hamiltonian Phase State (HPS) problem, which is the task of decoding output states of a random instantaneous quantum polynomial-time (IQP) circuit. Hamiltonian phase states can be generated very efficiently using only Hadamard gates, single-qubit Z-rotations and CNOT circuits. We provide evidence for the hardness of this assumption and show that it allows us to efficiently construct many pseudorandom quantum primitives, ranging from quantum pseudoentanglement, to pseudorandom unitaries, and even public-key encryption with quantum keys.
On the average-case complexity of learning output distributions of quantum circuits, Alexander Nietner, Marios Ioannou, Ryan Sweke, Richard Kueng, Jens Eisert, Marcel Hinsche, Jonas Haferkamp [arXiv]
Short description: In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on n qubits, we show there exists a depth d=O(n), such that any learning algorithm requires exponentially many queries to achieve even a tiny probability of success over the randomly drawn instance. We also show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with overwhelming probability, which confirms a variant of a conjecture by Aaronson and Chen.
Efficient unitary designs with a system-size independent number of non-Clifford gates, Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross, Ingo Roth, QIP 2022 [QIP] [arXiv] [Communications in mathematical physics]
Short description: The Clifford groups famously forms a unitary 3-design but gracefully fails to be a 4-design. In fact, no finite subgroup can form a 4-design as proven here. In this paper we build a bridge across this infamous 4-design barrier by showing that approximate t-designs can be generated with system-size independent number of non-Clifford gates. Strikingly, the density of non-Clifford gates is allowed to tend to zero!