Andrew Childs

Geometric locality is an important theoretical and practical factor for quantum low-density parity-check (qLDPC) codes which affects code performance and ease of physical realization. For device architectures restricted to 2D local gates, naively implementing the high-rate codes suitable for low-overhead fault-tolerant quantum computing incurs prohibitive overhead. In this work, we present an error correction protocol built on a bilayer architecture that aims to reduce operational overheads when restricted to 2D local gates by measuring some generators less frequently than others. We investigate the family of bivariate bicycle qLDPC codes and show that they are well suited for a parallel syndrome measurement scheme using fast routing with local operations and classical communication (LOCC). Through circuit-level simulations, we find that in some parameter regimes bivariate bicycle codes implemented with this protocol have logical error rates comparable to the surface code while using fewer physical qubits.

The so-called welded tree problem provides an example of a black-box problem that can be solved exponentially faster by a quantum walk than by any classical algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find another distinguished EXIT vertex using polynomially many queries, though without finding any particular path from ENTRANCE to EXIT. It has been an open problem for twenty years whether there is an efficient quantum algorithm for finding such a path, or if the path-finding problem is hard even for quantum computers. We show that a natural class of efficient quantum algorithms provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider algorithms that, within each branch of their superposition, always store a set of vertex labels that form a connected subgraph including the ENTRANCE, and that only provide these vertex labels as inputs to the oracle. While this does not rule out the possibility of a quantum algorithm that efficiently finds a path, it is unclear how an algorithm could benefit by deviating from this behavior. Our no-go result suggests that, for some problems, quantum algorithms must necessarily forget the path they take to reach a solution in order to outperform classical computation.

Abstract While the power of quantum computers remains far from well understood, many quantum algorithms have been developed that provide various degrees of improvement over classical computation. This tutorial will present an overview of some of the major quantum algorithms and quantum algorithmic techniques. Topics to be covered include quantum query algorithms and their limitations, algebraic quantum algorithms, quantum walk, and quantum algorithms for Hamiltonian simulation, high-dimensional linear algebra, and optimization.

Abstract A non-interactive zero-knowledge (NIZK) proof system for a language L in NP allows a prover (who is provided with an instance x and a witness w) to compute a classical certificate for the claim that x is in L, with the following properties: 1) the protocol can be verified efficiently, and 2) the protocol does not reveal any information about w, besides the fact that it exists (i.e., that x is in L). While NIZKs are known to be impossible in the plain model (i.e., with no additional trusted resource), they are well studied in alternative models and have seen widespread application in classical cryptography. Given the importance of NIZKs, and more generally zero-knowledge protocols, in classical cryptography, there has been a recent effort to achieve such protocols for QMA, a natural quantum analog of NP. However, all previous results only achieved interactive protocols, limiting their cryptographic use. Moreover, they all rely on quantum communication between the prover and the verifier, which may be difficult to achieve. In this submission, we present two NIZK protocols for QMA in the Common Reference String (CRS) model, with additional offline setup. Both protocols are achieved through the homomorphic computation of classical NIZKs for NP, and rely on the hardness of the Learning With Errors problem. However, each of them then combines this core idea with different (seemingly incomparable) techniques: 1) our first protocol makes use of quantum teleportation and quantum communication in an offline setup phase, with a classical online phase; our second protocol leverages techniques for classical verification of quantum computations, and is the only known NIZK for QMA to be completely classical, as well as reusable, meaning that a single setup allows to prove many theorems. Security of the latter is in the Quantum Random Oracle model.

Abstract Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup? In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups. In contrast, in the adjacency list model for bounded-degree graphswhere graph symmetry is manifested differentlywe exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013).

In a recent breakthrough, Mahadev constructed an interactive protocol that enables a purely classical party to delegate any quantum computation to an untrusted quantum prover. In this work, we show that this same task can in fact be performed non-interactively and in zero-knowledge. Our protocols result from a sequence of significant improvements to the original four-message protocol of Mahadev. We begin by making the first message instance-independent and moving it to an offline setup phase. We then establish a parallel repetition theorem for the resulting three-message protocol, with an asymptotically optimal rate. This, in turn, enables an application of the Fiat-Shamir heuristic, eliminating the second message and giving a non-interactive protocol. Finally, we employ classical non-interactive zero-knowledge (NIZK) arguments and classical fully homomorphic encryption (FHE) to give a zero-knowledge variant of this construction. This yields the first purely classical NIZK argument system for QMA, a quantum analogue of NP. We establish the security of our protocols under standard assumptions in quantum-secure cryptography. Specifically, our protocols are secure in the Quantum Random Oracle Model, under the assumption that Learning with Errors is quantumly hard. The NIZK construction also requires circuit-private FHE.

We study how efficiently a k-element set S subseteq [n] can be learned from a uniform superposition ket{S} of its elements. One can think of ket{S}=sum_{i in S} ket{i}/sqrt{|S|} as the quantum version of a uniformly random sample over S, as in the classical analysis of the “coupon collector problem.” We show that if k is close to n, then we can learn S using asymptotically fewer quantum samples than random samples. In particular, if there are n-k=O(1) missing elements then O(k) copies of ket{S} suffice, in contrast to the Theta(k log k) random samples needed by a classical coupon collector. On the other hand, if n-k=Omega(k), then Omega(k log k) quantum samples are necessary. More generally, we give tight bounds on the number of quantum samples needed for every k and n, and we give efficient quantum learning algorithms. We also give tight bounds in the model where we can additionally reflect through ket{S}. Finally, we relate coupon collection to a known example separating proper and improper PAC learning that turns out to show no separation in the quantum case.

In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes

Certifying the existence of entanglement between two parties is a fundamental problem in quantum information science. In this work, we develop a protocol for verifying that two parties located at specified positions share an entangled quantum state. We accomplish this by embedding the CHSH game in a quantum position verification protocol. This provides a form of entanglement testing that not only ensures that provers passing the protocol share entanglement, but that they are also located where they claim to be. This prevents parties from passing the verification test by simply forwarding the input of the verification protocol to other parties that share entanglement. The protocol has low requirements on the quantum computational abilities of honest provers---namely, it only requires the honest provers to manipulate two qubits each. It achieves security against adversaries located at incorrect positions that share at most a logarithmic amount of quantum memory with respect to the size of the classical input.

We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability.