Scaling bottlenecks the making of digital quantum computers, posing challenges from both the quantum and the classical components. We present a classical architecture to cope with a comprehensive list of the latter challenges all at once , and implement it fully in an end-to-end system by integrating a multi-core RISC-V CPU with our in-house control electronics. Our architecture enables scalable, high-precision control of large quantum processors and accommodates evolving requirements of quantum hardware. A central feature is a microarchitecture executing quantum operations in parallel on arbitrary predefined qubit groups. Another key feature is a reconfigurable quantum instruction set that supports easy qubit re-grouping and instructions extensions. As a demonstration, we implement the widely-studied surface code quantum computing workflow, which is instructive for being demanding on both the controllers and the integrated classical computation. Our design, for the first time, reduces instruction issuing and transmission costs to constants, which do not scale with the number of qubits, without adding any overheads in decoding or dispatching. Our system uses a dedicated general-purpose CPU for both qubit control and classical computation, including syndrome decoding. Implementing recent theoretical proposals as decoding firmware that parallelizes general inner decoders, we can achieve unprecedented decoding capabilities of up to distances 47 and 67 with the currently available systems-on-chips for physical error rate p = 0.001 and p = 0.0001, respectively, all in just 1 μs.

A prominent application of quantum cryptography is the distribution of cryptographic keys that are provably secure. Such security proofs were extended by Vazirani and Vidick (Physical Review Letters, 113, 140501, 2014) to the deviceindependent (DI) scenario, where the users do not need to trust the integrity of the underlying quantum devices. The protocols analyzed by them and by subsequent authors all require a sequential execution of N multiplayer games, where N is the security parameter. In this work, we prove the security of a protocol where all games are executed in parallel. Besides decreasing the number of time-steps necessary for key generation, this result reduces the security requirements for DI-QKD by allowing arbitrary information leakage of each user's inputs within his or her lab. To the best of our knowledge, this is the first parallel security proof for a fully device-independent QKD protocol. Our protocol tolerates a constant level of device imprecision and achieves a linear key rate.

Colbeck [ Ph.D. thesis, 2006] proposed using Bell inequality violations to generate certified random numbers. While full quantum-security proofs have been given, it remains a major open problem to identify the broadest class of Bell inequalities and lowest performance requirements to achieve such security. In this paper, working within the broad class of spot-checking protocols, we prove exactly which Bell inequality violations can be used to achieve full security. Our result greatly improves the known noise tolerance for secure randomness expansion: for the commonly used CHSH game, full security was only known with a noise tolerance of 1.5% [Miller and Shi, J. ACM, 63 (2016), 33], and we improve this to 10.3%. We also generalize our results beyond Bell inequalities and give the first security proof for randomness expansion based on Kochen--Specker inequalities. The central technical contribution of the paper is a new uncertainty principle for the Schatten norm, which is based on the uniform convexity inequality of Ball, Carlen, and Lieb [ Invent. Math., 115 (1994), pp. 463--482].

Randomness is a vital resource for modern-day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high-quality random numbers generated securely. Here, we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: cryptographic level of security, tolerating a constant level of imprecision in devices, requiring only unit size quantum memory (for each device component) in an honest implementation, and allowing a large natural class of constructions for the protocol. In conjunction with a recent work by Chung et al. [2014], it also leads to robust unbounded expansion using just 2 multipart devices. When adapted for distributing cryptographic keys, our method achieves, for the first time, exponential expansion combined with cryptographic security and noise tolerance. The proof proceeds by showing that the Rényi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements and a method for simulating trusted measurements with untrusted devices.

Randomness is a vital resource for modern day information processing, especially for cryptography. A wide range of applications critically rely on abundant, high quality random numbers generated securely. Here we show how to expand a random seed at an exponential rate without trusting the underlying quantum devices. Our approach is secure against the most general adversaries, and has the following new features: tolerating a constant level of implementation imprecision, requiring only a unit size quantum memory per device component for the honest implementation, and allowing a large natural class of constructions. In conjunct with a recent work by Chung, Shi and Wu (QIP 2014), it leads to robust unbounded expansion using just 2 multi-part devices. It can also be adapted for distributing cryptographic keys securely. The proof begins with a known protocol and proceeds by showing that the Renyi divergence of the outputs of the protocol (for a specific bounding operator) decreases linearly as the protocol iterates. At the heart of the proof are a new uncertainty principle on quantum measurements, and a method for simulating trusted measurements with untrusted devices. A full version of this paper containing additional results developed after the conference submission is available as arXiv:1402.0489.

We investigate the fundamental problem of generating bipartite classical distributions or quantum states. By designing efficient communication protocols and proving their optimality, we establish a number of intriguing connections to fundamental measures in optimization, convex geometry, and information theory. 1. To generate a classical distribution P(x, y), we tightly characterize the minimum amount of quantum communication needed by the psd-rank of P (as a matrix), a measure recently proposed by Fiorini, Massar, Pokutta, Tiwary and de Wolf (Proceedings of the 44th A CM Symposium on Theory of Computing, pages 95–106, 2012) in studies of the minimum size of extended formulations of optimization problems such as TSP. This echos the previous characterization for the optimal classical communication cost by the nonnegative rank of P. The result is obtained via investigating the more general case of bipartite quantum state generation and designing an optimal protocol for it. 2. When an approximation of ε is allowed to generate a distribution (X, Y) ∼ P, we present a classical protocol of the communication cost O((C(X, Y) + 1)/ε), where C(X, Y) is common information, a well-studied measure in information theory introduced by Wyner (IEEE Transactions on Information Theory, 21(2):163–179, 1975). This also links nonnegative rank and common information, two seemingly unrelated quantities in different fields. 3. For approximately generating a quantum pure state |ψ〉, we completely characterize the minimum cost by a corresponding approximate rank, closing a possibly exponential gap left in Ambainis, Schulman, Ta-Shma, Vazirani and Wigderson (SIAM Journal on Computing, 32(6):1570–1585, 2003).

We investigate the fundamental problem of generating bipartite classical distributions or quantum states. By designing efficient communication protocols and proving their optimality, we establish a number of intriguing connections to fundamental measures in optimization, convex geometry, and information theory. 1) To generate a classical distribution P(x,y), we tightly characterize the minimum amount of quantum communication needed by the psd-rank of P (as a matrix), a measure recently proposed by Fiorini et al. (Proc. 44th ACM Symp. Theory Comput., pp. 95-106, 2012) in studies of the minimum size of extended formulations of optimization problems such as TSP. This echos the previous characterization for the optimal classical communication cost by the nonnegative rank of P. The result is obtained via investigating the more general case of bipartite quantum state generation and designing an optimal protocol for it. 2) When an approximation ϵ is allowed to generate a distribution (X,Y)~P, we present a classical protocol of the communication cost O((C(X,Y)+1)/ϵ, where C(X,Y) is common information, a well-studied measure in information theory introduced by Wyner (IEEE Trans. Inf. Theory, 21 (2):163-179, 1975). This also links nonnegative rank and common information, two seemingly unrelated quantities in different fields. 3) For approximately generating a quantum pure state |ψ〉, we completely characterize the minimum cost by a corresponding approximate rank, closing a possibly exponential gap left in Ambainis etal. (SIAM J. Comput., 32 (6):1570-1585, 2003).

Bennett [PhysicalReviewA, vol. 59, no. 2, p. 1070, 1999] identified a set of orthogonal product states in the Hilbert space\BBC3otimes\BBC3such that reliably distinguishing those states requires nonlocal quantum operations. While more examples have been found for this counterintuitive ldquononlocality without entanglementrdquo phenomenon, a complete and computationally verifiable characterization for all such sets of states remains unknown. In this paper, we give such a characterization for both\BBC3otimes\BBC3and\BBC2otimes\BBC2otimes\BBC2. As a consequence, we show that in both spaces, there is no additional set of a fundamentally different structure than those of the known instances.

The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with T gates whose underlying graph has a treewidth d can be simulated deterministically in $T^{O(1)}\exp[O(d)]$ time, which, in particular, is polynomial in T if $d=O(\log T)$. Among many implications, we show efficient simulations for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also show that one-way quantum computation of Raussendorf and Briegel (Phys. Rev. Lett., 86 (2001), pp. 5188–5191), a universal quantum computation scheme with promising physical implementations, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph with a constant maximum degree. (The requirement on the maximum degree was removed in [I. L. Markov and Y. Shi, preprint:quant-ph/0511069].)

We initiate the study of quantifying nonlocality of a bipartite measurement by the minimum amount of classical communication required to simulate the measurement. We derive general upper bounds in terms of some tensor norms of the measurement operator. As applications, we show that (a) if the amount of communication is a constant, then quantum and classical communication protocols with an unlimited amount of shared entanglement or shared randomness compute the same class of functions; and (b) it requires only a constant amount of communication to classically generate an approximation of the output distribution resulting from local measurements on an entangled quantum state, as long as the number of measurement outcomes is a constant.

Nonlocality is at the heart of quantum information processing. In this paper we investigate the minimum amount of classical communication required to simulate a nonlocal quantum measurement. We derive general upper bounds, which in turn translate to systematic classical simulations of quantum communication protocols.As a concrete application, we prove that any quantum communication protocol with shared entanglement for computing a Boolean function can be simulated by a classical protocol whose cost does not depend on the amount of the shared entanglement. This implies that if the cost of communication is a constant, quantum and classical protocols, with shared entanglement and shared coins, respectively, compute the same class of functions.Furthermore, we describe a new class of efficient quantum communication protocols based on fast quantum algorithms. While some of them have efficient classical simulations by our method, others appear to be good candidates for separating quantum v.s. classical protocols, and quantum protocols with v.s. without shared entanglement.Yet another application is in the context of simulating quantum correlations using local hidden variable models augmented with classical communications. We give a constant cost, approximate simulation of quantum correlations when the number of correlated variables is a constant, while the dimension of the entanglement and the number of possible measurements can be arbitrary.Our upper bounds are expressed in terms of some tensor norms on the measurement operator. Those norms capture the nonlocality of bipartite operators in their own way and may be of independent interest and further applications.

Given a function f as an oracle, the collision problem is to find two distinct indexes i and j such that f ( i ) = f ( j ), under the promise that such indexes exist. Since the security of many fundamental cryptographic primitives depends on the hardness of finding collisions, our lower bounds provide evidence for the existence of cryptographic primitives that are immune to quantum cryptanalysis. We prove that any quantum algorithm for finding a collision in an r -to-one function must evaluate the function Ω(( n / r ) 1/3 ) times, where n is the size of the domain and r | n . This matches an upper bound of Brassard, Høyer, and Tapp. No lower bound better than constant was previously known. Our result also implies a quantum lower bound of Ω( n 2/3 ) queries for the element distinctness problem, which is to determine whether n integers are all distinct. The best previous lower bound was Ω(√ n ) queries.

Given a function f as an oracle, the collision problem is to find two distinct inputs i and j such that f(i)=f(j), under the promise that such inputs exist. In this paper, we prove that any quantum algorithm for finding a collision in an r-to-one function must evaluate the function /spl Omega/ ((n/r)/sup 1/3/) times, where n is the size of the domain and r|n. This lower bound matches, up to a constant factor, the upper bound of Brassard, Hoyer and Tapp (1997), which uses the quantum algorithm of Grover (1996) in a novel way. The previously best quantum lower bound is /spl Omega/ ((n/r)/sup 1/5/) evaluations, due to Aaronson (2002). Our result implies a quantum lower bound of /spl Omega/ (n/sup 2/3/) queries to the inputs for another well studied problem, the element distinctness problem, which is to determine whether or not the given n real numbers are distinct. The previous best lower bound is /spl Omega/ (/spl radic/n) queries in the black-box model; and /spl Omega/ (/spl radic/n log n) comparisons in the comparisons-only model, due to Hoyer Neerbek, and Shi (2001).

Given m copies of the same problem, does it take m times the amount of resources to solve these m problems? This is the direct sum problem, a fundamental question that has been studied in many computational models. We study this question in the simultaneous message (SM) model of communication introduced by A.C. Yao (1979). The equality problem for n-bit strings is well known to have SM complexity /spl Theta/(/spl radic/n). We prove that solving m copies of the problem has complexity /spl Omega/(m/spl radic/n); the best lower bound provable using previously known techniques is /spl Omega/(/spl radic/(mn)). We also prove similar lower bounds on certain Boolean combinations of multiple copies of the equality function. These results can be generalized to a broader class of functions. We introduce a new notion of informational complexity which is related to SM complexity and has nice direct sum properties. This notion is used as a tool to prove the above results; it appears to be quite powerful and may be of independent interest.

We prove new results on evasiveness of monotone graph properties by extending the techniques of Kahn, Saks, and Sturtevant [Combinatorica, 4 (1984), pp. 297--306]. For the property of containing a subgraph isomorphic to a fixed graph, and a fairly large class of related n-vertex graph properties, we show evasiveness for an arithmetic progression of values of n. This implies a $\frac12n^2 - O(n)$ lower bound on the decision tree complexity of these properties. We prove that properties that are preserved under taking graph minors are evasive for all sufficiently large n. This greatly generalizes a theorem due to Best, van Emde Boas, and Lenstra [A Sharpened Version of the Aanderaa--Rosenberg Conjecture, Report ZW 30/74, Mathematisch Centrum, Amsterdam, The Netherlands, 1974] which states that planarity is evasive. We prove a similar result for bipartite subgraph containment.