Arrow Research search

Author name cluster

Henry Yuen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

14 papers
1 author row

Possible papers

14

FOCS Conference 2024 Conference Paper

Simple Constructions of Linear-Depth t-Designs and Pseudorandom Unitaries

  • Tony Metger
  • Alexander Poremba
  • Makrand Sinha
  • Henry Yuen

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 research into random unitaries that “look” sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: $t$ -designs are random unitaries that information-theoretically reproduce the first $t$ moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random. In this work, we take a unified approach to constructing $t$ -designs and PRUs. For this, we introduce and analyse the “ $PFC$ ensemble”, the product of a random computational basis permutation $P$, a random binary phase operator $F$, and a random Clifford unitary $C$. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the $PFC$ ensemble to show the following: •Linear-depth $t$ -designs. We give the first construction of a (diamond-error) approximate $t$ -design with circuit depth linear in $t$. This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their $2t$ -wise independent counterparts. •Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i. e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the $PFC$ ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. •Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from $n$ to $n+\omega(\log n)$ qubits, a small modification of our PRU construction achieves adaptive security, i. e. even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.

Details

FOCS Conference 2023 Conference Paper

stateQIP = statePSPACE

  • Tony Metger
  • Henry Yuen

Complexity theory traditionally studies the hardness of solving classical computational problems. In the quantum setting, it is also natural to consider a different notion of complexity, namely the complexity of physically preparing a certain quantum state. We study the relation between two such state complexity classes: statePSPACE, which contains states that can be generated by space-uniform polynomial-space quantum circuits, and stateQIP, which contains states that a polynomialtime quantum verifier can generate by interacting with an all-powerful untrusted quantum prover. The latter class was recently introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE $\subseteq$ stateQIP. Our main result is the reverse inclusion, stateQIP $\subseteq$ statePSPACE, thereby establishing equality of the two classes and providing a natural state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum algorithm for solving a large class of exponentially large “PSPACE-computable” semidefinite programs (SDPs), which also prepares an optimiser encoded in a quantum state. Our SDP solver relies on recent blockencoding techniques from quantum algorithms, demonstrating that these techniques are also useful for complexity theory. Using similar techniques, we also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum polynomial space. We prove this by studying an algorithmic version of Uhlmann’s theorem and establishing an upper bound on the complexity of implementing Uhlmann transformations.

Details

STOC Conference 2022 Conference Paper

Quantum garbled circuits

  • Zvika Brakerski
  • Henry Yuen

In classical computing, garbled circuits (and their generalization known as randomized encodings) are a versatile cryptographic tool with many applications such as secure multiparty computation, delegated computation, depth-reduction of cryptographic primitives, complexity lower-bounds, and more. Quantum analogues of garbled circuits were not known prior to this work. In this work, we introduce a definition of quantum randomized encodings and present a construction which allows us to efficiently garble any quantum circuit, assuming the existence of quantum-secure one-way functions. Our construction has comparable properties to the best known classical garbling schemes. We can also achieve perfect information-theoretic security albeit with blowup in the size of the garbled circuits. We believe that quantum garbled circuits and quantum randomized encodings can be an instrumental concept and building block for quantum computation and in particular quantum cryptography. We present some applications, including a conceptually-simple zero-knowledge proof system for QMA, a protocol for private simultaneous messages, functional encryption, and more.

Details

FOCS Conference 2021 Conference Paper

Quantum soundness of testing tensor codes

  • Zhengfeng Ji
  • Anand Natarajan 0001
  • Thomas Vidick
  • John Wright 0004
  • Henry Yuen

A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of Reed-Muller codes. The natural test for tensor codes, the axis-parallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. We analyze the axis-parallel line vs. point test as a two-prover game and show that the test is sound against quantum provers sharing entanglement. Our result implies the quantum-soundness of the low individual degree test, which is an essential component of the MIP* = RE theorem. Our proof also generalizes to the infinite-dimensional commuting-operator model of quantum provers.

Details

FOCS Conference 2019 Conference Paper

Perfect Zero Knowledge for Quantum Multiprover Interactive Proofs

  • Alex Bredariol Grilo
  • William Slofstra
  • Henry Yuen

In this work we consider the interplay between multiprover interactive proofs, quantum entanglement, and zero knowledge proofs - notions that are central pillars of complexity theory, quantum information and cryptography. In particular, we study the relationship between the complexity class MIP*, the set of languages decidable by multiprover interactive proofs with quantumly entangled provers, and the class PZK-MIP*, which is the set of languages decidable by MIP* protocols that furthermore possess the perfect zero knowledge property. Our main result is that the two classes are equal, i. e. , MIP* = PZK-MIP*. This result provides a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC 1988) who show that MIP = PZK-MIP (in other words, all classical multiprover interactive protocols can be made zero knowledge). We prove our result by showing that every MIP* protocol can be efficiently transformed into an equivalent zero knowledge MIP* protocol in a manner that preserves the completeness-soundness gap. Combining our transformation with previous results, we obtain the corollaries that i) all languages that can be solved in non-deterministic double exponential time have zero knowledge MIP* protocols and ii) all co-recursively enumerable languages (which include undecidable problems as well as all decidable problems) have zero knowledge MIP* protocols with vanishing promise gap.

Details

STOC Conference 2017 Conference Paper

Hardness amplification for entangled games via anchoring

  • Mohammad Bavarian
  • Thomas Vidick
  • Henry Yuen

We study the parallel repetition of one-round games involving players that can use quantum entanglement. A major open question in this area is whether parallel repetition reduces the entangled value of a game at an exponential rate - in other words, does an analogue of Raz's parallel repetition theorem hold for games with players sharing quantum entanglement? Previous results only apply to special classes of games. We introduce a class of games we call anchored . We then introduce a simple transformation on games called anchoring , inspired in part by the Feige-Kilian transformation, that turns any (multiplayer) game into an anchored game. Unlike the Feige-Kilian transformation, our anchoring transformation is completeness preserving. We prove an exponential-decay parallel repetition theorem for anchored games that involve any number of entangled players. We also prove a threshold version of our parallel repetition theorem for anchored games. Together, our parallel repetition theorems and anchoring transformation provide the first hardness amplification techniques for general entangled games. We give an application to the games version of the Quantum PCP Conjecture.

Details

STOC Conference 2014 Conference Paper

Infinite randomness expansion with a constant number of devices

  • Matthew Coudron
  • Henry Yuen

We present a device-independent randomness expansion protocol, involving only a constant number of non-signaling quantum devices, that achieves infinite expansion : starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is exp(--Ω( m 1/3 ))-close to uniform and secure against a quantum adversary. The only parameters which depend on the size of the input are the soundness of the protocol and the security of the output (both are inverse exponential in m ). This settles a long-standing open problem in the area of randomness expansion and device-independence. The analysis of our protocols involves overcoming fundamental challenges in the study of adaptive device-independent protocols. Our primary technical contribution is the design and analysis of device-independent protocols which are Input Secure ; that is, their output is guaranteed to be secure against a quantum eavesdropper, even if the input randomness was generated by that same eavesdropper ! The notion of Input Security may be of independent interest to other areas such as device-independent quantum key distribution.

Details