Fermi Ma

STOC Conference 2025 Conference Paper

How to Construct Random Unitaries

• Fermi Ma
• Hsin-Yuan Huang

The existence of pseudorandom unitaries (PRUs)—efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries—has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary U , and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary U and its inverse U † . In the process, we prove that any algorithm making queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.

STOC Conference 2024 Conference Paper

A One-Query Lower Bound for Unitary Synthesis and Breaking Quantum Cryptography

• Alex Lombardi
• Fermi Ma
• John Wright 0004

The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n -qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f . In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function? In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm A f can implement U , even approximately, if it only makes one (quantum) query to f . Our approach also has implications for quantum cryptography: we prove (relative to a random oracle) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries A f . Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, our result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks. To prove this result, we formulate unitary synthesis as an efficient challenger-adversary game, which enables proving lower bounds by analyzing the maximum success probability of an adversary A f . Our main technical insight is to identify a natural spectral relaxation of the one-query optimization problem, which we bound using tools from random matrix theory. We view our framework as a potential avenue to rule out polynomial-query unitary synthesis, and we state conjectures in this direction.

STOC Conference 2023 Conference Paper

Commitments to Quantum States

• Sam Gunn
• Nathan Ju
• Fermi Ma
• Mark Zhandry

FOCS Conference 2022 Conference Paper

Post-Quantum Zero Knowledge, Revisited or: How to Do Quantum Rewinding Undetectably

• Alex Lombardi
• Fermi Ma
• Nicholas Spooner

When do classical zero-knowledge protocols remain secure against quantum attacks? In this work, we develop the techniques, tools, and abstractions necessary to answer this question for foundational protocols: 1)We prove that the Goldreich-Micali-Wigderson protocol for graph non-isomorphism and the Feige-Shamir protocol for NP remain zero-knowledge against quantum adversaries. At the heart of our proof is a new quantum rewinding technique that enables extracting information from multiple invocations of a quantum adversary without disturbing its state. 2)We prove that the Goldreich-Kahan protocol for NP is post-quantum zero knowledge using a simulator that can be seen as a natural quantum extension of the classical simulator. Our results achieve negligible simulation error, appearing to contradict a recent impossibility result due to Chia-Chung-Liu-Yamakawa (FOCS 2021). This brings us to our final contribution: 3. We introduce coherent-runtime expected quantum polynomial time, a simulation notion that (a) precisely captures all of our zero-knowledge simulators, (b) cannot break any polynomial hardness assumptions, (c) implies strict polynomial-time ε-simulation and (d) is not subject to the CCLY impossibility. In light of our positive results and the CCLY negative results, we propose coherent-runtime simulation to be the appropriate quantum analogue of classical expected polynomial-time simulation.

FOCS Conference 2021 Conference Paper

Post-Quantum Succinct Arguments: Breaking the Quantum Rewinding Barrier

• Alessandro Chiesa
• Fermi Ma
• Nicholas Spooner
• Mark Zhandry

We prove that Kilian's four-message succinct argument system is post-quantum secure in the standard model when instantiated with any probabilistically checkable proof and any collapsing hash function (which in turn exist based on the post-quantum hardness of Learning with Errors). This yields the first post-quantum succinct argument system from any falsifiable assumption. At the heart of our proof is a new quantum rewinding procedure that enables a reduction to repeatedly query a quantum adversary for accepting transcripts as many times as desired. Prior techniques were limited to a constant number of accepting transcripts.

TCS Journal 2018 Journal Article

The fewest clues problem

• Erik D. Demaine
• Fermi Ma
• Ariel Schvartzman
• Erik Waingarten
• Scott Aaronson

When analyzing the computational complexity of well-known puzzles, most papers consider the algorithmic challenge of solving a given instance of (a generalized form of) the puzzle. We take a different approach by analyzing the computational complexity of designing a “good” puzzle. We assume a puzzle maker designs part of an instance, but before publishing it, wants to ensure that the puzzle has a unique solution. Given a puzzle, we introduce the FCP (fewest clues problem) version of the problem: Given an instance to a puzzle, what is the minimum number of clues we must add in order to make the instance uniquely solvable? We analyze this question for the Nikoli puzzles Sudoku, Shakashaka, and Akari. Solving these puzzles is NP-complete, and we show their FCP versions are Σ 2 P -complete. Along the way, we show that the FCP versions of Triangle Partition, Planar 1-in-3 SAT, and Latin Square are all Σ 2 P -complete. We show that even problems in P have difficult FCP versions, sometimes even Σ 2 P -complete, though “closed under cluing” problems are in the (presumably) smaller class NP; for example, FCP 2SAT is NP-complete.