TQC · 2020

Due to Csiszar and Koerner, the capacity of classical wiretap channels has a single-letter characterization in terms of the private information. For quantum wiretap channels, however, it is known that regularization of the private information is necessary to reach the capacity. Here, we study hybrid classical-quantum wiretap channels in order to resolve to what extent quantum effects are needed to witness non-additivity phenomena in quantum Shannon theory. For wiretap channels with quantum inputs but classical outputs, we prove that the characterization of the capacity in terms of the private information stays single-letter. Hence, entangled input states are of no asymptotic advantage in this setting. For wiretap channels with classical inputs, we show by means of explicit examples that the private information already becomes non-additive when either one of the two receivers becomes quantum (with the other receiver staying classical). This gives non-additivity examples that are not caused by entanglement and illustrates that quantum adversaries are strictly different from classical adversaries in the wiretap model.

We prove tight lower bounds for the following variant of the counting problem considered by Aaronson \etal. The task is to distinguish whether an input set $x\subseteq [n]$ has size either $k$ or $k’=(1+\epsilon)k$. We assume the algorithm has access to

We study quantum algorithms for problems in computational geometry, such as Point-On-3-Lines problem. In this problem, we are given a set of lines and we are asked to find a point that lies on at least 3 of these lines. Point-On-3-Lines and many other computational geometry problems are known to be 3Sum-Hard. That is, solving them classically requires time \Omega(n^{2-o(1)}), unless there is faster algorithm for the well known 3Sum problem (in which we are given a set S of n integers and have to determine if there are a, b, c \in S such that a + b + c = 0). Quantumly, 3Sum can be solved in time O(n log n) using Grover’s quantum search algorithm. This leads to a question: can we solve Point-On-3-Lines and other 3Sum-Hard problems in O(n^c) time quantumly, for c<2? We answer this question affirmatively, by constructing a quantum algorithm that solves Point-On-3-Lines in time O(n^{1 + o(1)}). The algorithm combines recursive use of amplitude amplification with geometrical ideas. We show that the same ideas give O(n^{1 + o(1)}) time algorithm for many 3Sum-Hard geometrical problems.

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 this work we develop new methods for the characterisation of continuous variable quantum states using heterodyne measurement in both the trusted and untrusted settings. First, building on quantum state tomography with heterodyne detection, we introduce a reliable method for continuous variable quantum state certication, which directly yields the elements of the density matrix of the state considered and analytical condence intervals. This method neither needs mathematical reconstruction of the data, nor discrete binning of the sample space, and uses a single Gaussian measurement setting. Second, beyond quantum state tomography and without its identical copies assumption, we promote our reliable tomography method to a general efficient protocol for verifying continuous variable pure quantum states with Gaussian measurements against fully malicious adversaries, i.e. making no assumptions whatsoever on the state generated by the adversary. These results are obtained using a new analytical estimator for the expected value of any operator acting on a continuous variable quantum state with bounded support over the Fock basis, computed with samples from heterodyne detection of the state.

We introduce spectral quantum tomography, a simple method to extract the eigenvalues of a noisy few-qubit gate, represented by a trace-preserving superoperator, in a SPAM-resistant fashion, using low resources in terms of gate sequence length. The eigenvalues provide detailed gate information, supplementary to known gate-quality measures such as the gate fidelity, and can be used as a gate diagnostic tool. We apply our method to one- and two-qubit gates on two different superconducting systems available in the cloud, namely the QuTech Quantum Infinity and the IBM Quantum Experience. We discuss how cross-talk, leakage and non-Markovian errors affect the eigenvalue data.

Knabe’s theorem lower bounds the spectral gap of a one dimensional frustration-free local hamiltonian in terms of the local spectral gaps of finite regions. It also provides a local spectral gap threshold for hamiltonians that are gapless in the thermodynamic limit, showing that the local spectral gap much scale inverse linearly with the length of the region for such systems. Recent works have further improved upon this threshold, tightening it in the one dimensional case and extending it to higher dimensions. Here, we show a local spectral gap threshold for frustration-free hamiltonians on a finite dimensional lattice, that is optimal up to a constant factor that depends on the dimension of the lattice. Our proof is based on the detectability lemma framework and uses the notion of coarse-grained hamiltonian (introduced in [Phys. Rev. B 93, 205142]) as a link connecting the (global) spectral gap and the local spectral gap.

We consider a computational problem where the goal is to approximate the maximum eigenvalue of a two-local Hamiltonian that describes antiferromagnetic Heisenberg interactions between qubits located at the vertices of the graph. Previous work has shed light on this problem’s approximability by \textit{product states}. For any instance of this problem the maximum energy attained by a product state is lower bounded by the Max Cut of the graph and upper bounded by the standard Goemans-Williamson semidefinite programming relaxation of it. Gharibian and Parekh described an efficient classical approximation algorithm for this problem which outputs a product state with energy at least $0.498$ times the maximum eigenvalue in the worst case, and observe that there exist instances where the best product state has energy $1/2$ of optimal. We investigate approximation algorithms with performance exceeding this limitation which are based on optimizing over tensor products of few-qubit states and shallow quantum circuits. We provide an efficient classical algorithm which achieves an approximation ratio of at least $0.53$ in the worst case. We also show that for any instance defined by a $3$ or $4$-regular triangle-free graph, there is an efficiently computable shallow quantum circuit that prepares a state with energy larger than the best product state (larger even than its semidefinite programming relaxation).

We present algorithms to evaluate partition functions of quantum Hamiltonians using mixed-state quantum computation, specifically the DQC1 model of computation which requires only one pure qubit. Our algorithm provides an additive-error estimate to the normalized partition function in time that is polynomial in the number of qubits, for a large class of Hamiltonians. This implies that a variant of the partition function problem, that was previously shown to be hard for the complexity class DQC1 by Brandao, is in fact DQC1-complete. Our algorithm is based on approximations of the exponential operator as linear combinations of unitaries, which are related to block-encoding of Hamiltonians or Hamiltonian evolutions. We then extend our results to give an algorithm that estimates the partition function within a desired relative error. Towards this end, we develop a procedure based on a sequence of approximations within predetermined additive errors that may be of independent interest.

Quantum Annealing and the Quantum Approximate Optimization Algorithm (QAOA) are both instances of the same control problem in which a combination of two Hamiltonians is applied to minimize the energy of a quantum state. Previous work has suggested that the bang-bang structure of QAOA is optimal but with significant caveats, leaving open the question of what procedure is optimal in practice. In this work, we formalize the optimal control arguments proving that a time-constrained procedure has a bang at the beginning and end but can take on an annealing-like form in-between. In numerics on transverse field Ising models, we show that bang-anneal-bang procedures are common with optimal time-constrained QAOA Trotterizing the annealing portion. We furthermore show an equivalence between different types of time-constraints in this style of problem. The optimal procedures we find are far removed from a monotonically changing adiabatic path in the short-time limit, but we show that as the allowed time increases, the adiabatic limit and intuition from adiabatic quantum computing apply.

Quantum computation promises significant computational advantages over classical computation for some problems. However, quantum hardware suffers from much higher error rates than in classical hardware. As a result, extensive quantum error correction is required to execute a useful quantum algorithm. The decoder is a key component of the error correction scheme whose role is to identify errors faster than they accumulate in the quantum computer and that must be implemented with minimum hardware resources in order to scale to the regime of practical applications. In this work, we consider surface code error correction, which is the most popular family of error correcting codes for quantum computing, and we design a decoder micro-architecture for the Union-Find decoding algorithm. We propose a three-stage fully pipelined hardware implementation of the decoder that significantly speeds up the decoder. Then, we optimize the amount of decoding hardware required to perform error correction simultaneously over all the logical qubits of the quantum computer. By sharing resources between logical qubits, we obtain a 67% reduction of the number of hardware units and the memory capacity is reduced by 70%. Moreover, we reduce the bandwidth required for the decoding process by a factor at least 30x using low-overhead compression algorithms. Finally, we provide numerical evidence that our optimized micro-architecture can be executed fast enough to correct errors in a quantum computer.

In fault-tolerant quantum computing systems, realising (approximately) universal quantum computation is usually described in terms of realising Clifford+T operations, which is to say a circuit of CNOT, Hadamard, and pi/2-phase rotations, together with T operations (pi/4-phase rotations). For many error correcting codes, fault-tolerant realisations of Clifford operations are significantly less resource-intensive than those of T gates, which motivates finding ways to realise the same transformation involving T-count (the number of T gates involved) which is as low as possible. Investigations into this problem has led to observations that this problem is closely related to NP-hard tensor decomposition problems and is tantamount to the difficult problem of decoding exponentially long Reed-Muller codes. This problem then presents itself as one for which must be content in practise with approximate optimisation, in which one develops an array of tactics to be deployed through some pragmatic strategy. In this vein, we describe techniques to reduce the T-count, based on the effective application of “spider nest identities”: easily recognised products of parity-phase operations which are equivalent to the identity operation. We demonstrate the effectiveness of such techniques by obtaining improvements in the T-counts of a number of circuits, in run-times which are typically less than the time required to make a fresh cup of coffee.

In locally interacting quantum many-body systems, a velocity of the information propagation is finitely bounded and the linear light cone can be defined. Outside the light cone, amount of the information propagation rapidly decays with the distance. When systems have long-range interactions, it is highly nontrivial whether such a linear light cone exists or not. We herein consider generic long-range interacting systems with decaying interactions as $R^{-\alpha}$ with the distance $R$. We rigorously prove the existence of the linear light cone for $\alpha>2D+1$ ($D$: the spatial dimension), where we obtain the Lieb-Robinson bound as $\|[O_i(t),O_j]\| < t^{2D+1}(R-\bar{v}t)^{-\alpha}$ with $\bar{v}=O(1)$ for arbitrary two operators $O_i$ and $O_j$ separated by a distance $R$. Moreover, we give an explicit quantum-state transfer protocol that achieves the above bound up to a constant coefficient and violates the linear light cone for $\alpha<2D+1$. This implies that our Lieb-Robinson bound is the best general upper bound in the regime of $\alpha>2D+1$.

The multiscale entanglement renormalization ansatz describes quantum many-body states by a hierarchical entanglement structure organized by length scale. Numerically, it has been demonstrated to capture critical lattice models and the data of the corresponding conformal field theories with high accuracy. However, a rigorous understanding of its success and precise relation to the continuum is still lacking. To address this challenge, we provide an explicit construction of entanglement-renormalization quantum circuits that rigorously approximate correlation functions of the massless Dirac conformal field theory. We directly target the continuum theory: discreteness is introduced by our choice of how to probe the system, not by any underlying short-distance lattice regulator. To achieve this, we use multiresolution analysis from wavelet theory to obtain an approximation scheme and to implement entanglement renormalization in a natural way. This could be a starting point for constructing quantum circuit approximations for more general conformal field theories.

The mixing time of Markovian dissipative evolutions of open quantum many-body systems can be bounded using optimal constants of certain quantum functional inequalities, such as the modified logarithmic Sobolev constant. For classical spin systems, the positivity of such constants follows from a mixing condition for the Gibbs measure, via quasi-factorization results for the entropy. Inspired by the classical case, we present a strategy to derive the positivity of the modified logarithmic Sobolev constant associated to the dynamics of certain quantum systems from some clustering conditions on the Gibbs state of a local, commuting Hamiltonian. In particular we show that for the heat-bath dynamics for 1D systems, the modified logarithmic Sobolev constant is positive under the assumptions of a mixing condition on the Gibbs state and a strong quasi-factorization of the relative entropy.

Braiding defects in topological stabiliser codes has been widely studied as a promising approach to fault-tolerant quantum computing. Here, we explore the potential and limitations of such schemes in codes of all spatial dimensions. We prove that a universal gate set for quantum computing cannot be realised by supplementing locality-preserving logical operators with defect braiding, even in more than two dimensions. However, notwithstanding this no-go theorem, we demonstrate that higher dimensional defect-braiding schemes have the potential to play an important role in realising fault-tolerant quantum computing. Specifically, we present an approach to implement the full Clifford group via braiding in any code possessing twist defects on which a fermion can condense. We explore three such examples in higher dimensional codes, specifically: in self-dual surface codes; the three dimensional Levin-Wen fermion model; and the checkerboard model. Finally, we show how our no-go theorems can be circumvented to provide a universal scheme in three-dimensional surface codes without magic state distillation.

It has long been known that long-ranged entangled topological phases can be exploited to protect quantum information against unwanted local errors. Indeed, conditions for intrinsic topological order are reminiscent of criteria for faithful quantum error correction. At the same time, the promise of using general topological orders for practical error correction remains largely unfulfilled to date. In this work, we significantly contribute to establishing such a connection by showing that Abelian twisted quantum double models can be used for quantum error correction. By exploiting the group cohomological data sitting at the heart of these lattice models, we transmute the terms of these Hamiltonians into full-rank, pairwise commuting operators, defining commuting stabilizers. The resulting codes are defined by non-Pauli commuting stabilizers, with local systems that can either be qubits or higher dimensional quantum systems. Thus, this work establishes a new connection between condensed matter physics and quantum information theory, and constructs tools to systematically devise new topological quantum error correcting codes beyond toric or surface code models.

In the stabilizer circuit model of quantum computation, universality requires a resource known as magic. Here, we propose three new ways to quantify the magic of a quantum state using magic monotones, apply the monotones in the characterization of state conversions under stabilizer operations, and connect them with the classical simulation of quantum circuits. We first present a complete theory of these quantifiers for tensor products of single-qubit states, for which the monotones are all equal and all act multiplicatively, constituting the first qubit magic monotones to have this property. We use the monotones to establish several asymptotic and non-asymptotic bounds on state interconversion and distillation rates. We then relate our quantifiers directly to the runtime of classical simulation algorithms, showing that a large amount of magic is a necessary requirement for any quantum speedup. One of our classical simulation algorithms is a quasi-probability simulator with its runtime connected to a generalized notion of negativity, which is exponentially faster than all prior qubit quasi-probability simulation algorithms. We also introduce a new variant of the stabilizer rank simulation algorithm suitable for mixed states, while improving the runtime bounds for this class of simulations. Our work reveals interesting connections between quasi-probability and stabilizer rank simulators, which previously appeared to be unrelated. Generalizing the approach beyond the theory of magic states, we establish methods for the quantitative characterization of classical simulability for more general quantum resources, and use them in the resource theory of quantum coherence to connect the L1-norm of coherence with the simulation of free operations.

A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver, against a linear number of adaptive queries to the token, in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the “prepare-and-measure” type. We also show our scheme is “tight” according to two scenarios.

Quantum information is well-known to achieve cryptographic feats that are unattainable using classical information alone. Here, we add to this repertoire by introducing a new cryptographic functionality called uncloneable encryption. This functionality allows the encryption of a classical message such that two collaborating but isolated adversaries are prevented from simultaneously recovering the message, even when the encryption key is revealed. Clearly, such functionality is unattainable using classical information alone. We formally define uncloneable encryption, and show how to achieve it using Wiesner’s conjugate coding, combined with a quantum-secure pseudorandom function (qPRF). Modelling the qPRF as an oracle, we show security by adapting techniques from the quantum one-way-to-hiding lemma, as well as using bounds from quantum monogamy-of-entanglement games.

The class MIP^* is the set of languages that are decidable by a multiprover interactive proof with quantum entangled provers. It was recently shown by Ji, Natarajan, Vidick, Wright and Yuen that MIP^* is equal to RE, the set of recursively enumerable languages. In particular this showed that the complexity of approximating the quantum value of a non-local game G is, in general, equivalent to the complexity of the Halting problem. In this paper we investigate the complexity of deciding whether the quantum value of a non-local game G is 1. This problem corresponds to a complexity class that we call zero gap MIP^*, denoted by MIP^*_0, where there is no promise gap between the verifier’s acceptance probabilities in the YES and NO cases. We prove that MIP^*_0 extends beyond the first level of the arithmetical hierarchy (which includes RE and its complement coRE), and in fact is equal to PI^0_2, the class of languages that can be decided by quantified formulas of the form for all y, there exists z, R(x,y,z). Combined with the previously known result that MIP^co_0, the commuting operator variant of MIP^*_0, is equal to coRE, our result further highlights the fascinating connection between various models of quantum multiprover interactive proofs and different classes in computability theory.

Communication networks have multiple users, each sending and receiving messages. A multiple access channel (MAC) models multiple senders transmitting to a single receiver, such as the uplink from many mobile phones to a single base station. The optimal performance of a MAC is quantified by a capacity region of simultaneously achievable communication rates. We study the two-sender classical MAC, the simplest and best-understood network, and find a surprising richness in both a classical and quantum context. First, we find that quantum entanglement shared between senders can substantially boost the capacity of a classical MAC. Second, we find that optimal performance of a MAC with bounded-size inputs may require unbounded amounts of entanglement. Third, determining whether a perfect communication rate is achievable using finite-dimensional entanglement is undecidable. Finally, we show that evaluating the capacity region of a two-sender classical MAC is in fact NP-hard.

When transforming pairs of independent quantum operations according to the fundamental rules of quantum theory, an intriguing phenomenon emerges: some such higher-order operations may act on the input operations in an indefinite causal order. Recently, the formalism of process matrices has been developed to investigate these noncausal properties of higher-order operations. This formalism predicts, in principle, statistics that ensure indefinite causal order even in a device-independent scenario, where the involved operations are not characterised. Nevertheless, all physical implementations of process matrices proposed so far require full characterisation of the involved operations in order to certify such phenomena. Here we consider a semi-device-independent scenario, which does not require all operations to be characterised. We introduce a framework for certifying noncausal properties of process matrices in this intermediate regime and use it to analyse the quantum switch, a well-known higher-order operation, to show that, although it can only lead to causal statistics in a device-independent scenario, it can exhibit noncausal properties in semi-device-independent scenarios. This proves that the quantum switch generates stronger noncausal correlations than it was previously known.

We study the problem of estimating distance measures between unknown quantum states, given M and N copies of each type. For pure states, any distance measure can be expressed in terms of the overlap between the states. Overlap estimation is a fundamental primitive in quantum information processing that is commonly accomplished from the outcomes of N swap-tests, a joint measurement on one copy of each type whose outcome probability is a linear function of the overlap. We show that a more precise estimate can be obtained by allowing for general collective measurements on all copies, in particular using weak Schur sampling. We derive the statistics of the optimal measurement and compute the optimal mean square error in the asymptotic pointwise and finite Bayesian estimation settings. Besides, we consider two strategies relying on the estimation of one or both the states, and show that, although they are suboptimal, they outperform the swap test. In particular, the swap test is extremely inefficient for small values of the overlap, which become exponentially more likely as the dimension increases. We show that the optimal measurement is less invasive than the swap test and study the robustness to depolarizing noise for qubit states. In the case of mixed states, distance measure cannot be expressed in terms of a single distance. With the swap test, one can estimate the Hilbert-Schmidt distance and the overlap, but it is not possible to obtain other very relevant distance measures. We show that simultaneous weak Schur sampling can instead estimate the spectra of each of the states and of their convex combination, with weight given by M/M+N and N/M+N. This estimate is much more informative than the outcome of swap tests and it can be used to estimate a wider class of properties and distinguishability measures. In particular we show how to measure the Holevo quantity of a an ensemble constructed with the states. We discuss how to get bounds on the trace distance using these estimates, and apply these bounds to closeness and remoteness testing, improving sample complexity with respect to the swap test.

A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer. There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g.\ using Shor’s algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g.\ BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii). In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.) We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration.

Self-testing is a method to characterise an arbitrary quantum system based only on its classical input-output correlations. This usually requires the assumption that the system’s state is shared among multiple parties that only perform local measurements and cannot communicate. Here, we replace the setting of multiple non-communicating parties, which is difficult to enforce in practice, by a single computationally bounded party. Specifically, we construct a protocol that allows a classical verifier to robustly certify that a single computationally bounded quantum device must have prepared a Bell pair and performed single-qubit measurements on it, up to a change of basis applied to both the device’s state and measurements. This means that under computational assumptions, the verifier is able to certify the presence of entanglement inside a single quantum device. We achieve this using techniques introduced by Brakerski et al. (2018) and Mahadev (2018) which allow a classical verifier to constrain the actions of a quantum device assuming the device does not break post-quantum cryptography.

A new bound for the quantum capacity of the d-dimensional depolarizing channels is presented. Our derivation makes use of a flagged extension of the map where the receiver obtains a copy of a state σ_0 whenever the messages are transmitted without errors, and a copy of a state σ_1 when instead the original state gets fully depolarized. By varying the overlap between the flag states, the resulting transformation nicely interpolates between the depolarizing map (when σ_0 = σ_1), and the d-dimensional erasure channel (when σ_0 and σ_1 have orthogonal support). We find sufficient conditions for degradability of the flagged channel, which let us to calculate its quantum capacity in a suitable parameter region. From this last result we get the upper bound for the depolarizing channel, which by a direct comparison appears to be tighter than previous available results for d > 2, and for d = 2 it is tighter in an intermediate regime of noise. In particular, in the limit of large d values, our findings presents a previously unnoticed O(1) correction.

We introduce and analyse the problem of encoding classical information into different resources of a quantum state. More precisely, we consider a general class of communication scenarios characterised by encoding operations that commute with a unique resource destroying map and leave free states invariant. Our motivating example is given by encoding information into coherences of a quantum system with respect to a fixed basis (with unitaries diagonal in that basis as encodings and the decoherence channel as a resource destroying map), but the generality of the framework allows us to explore applications ranging from super-dense coding to thermodynamics. For any state, we find that the number of messages that can be encoded into it using such operations in a one-shot scenario is upper-bounded in terms of the information spectrum relative entropy between the given state and its version with erased resources. Furthermore, if the resource destroying map is a twirling channel over some unitary group, we find matching one-shot lower-bounds as well. In the asymptotic setting where we encode into many copies of the resource state, our bounds yield an operational interpretation of resource monotones such as the relative entropy of coherence and its corresponding relative entropy variance.

Recently, Anshu et al. introduced “partially” smoothed information measures and used them to derive tighter bounds for several information-processing tasks, including quantum state merging and privacy amplification against quantum adversaries [arXiv:1807.05630 [quant-ph]]. Yet, a tight second-order asymptotic expansion of the partially smoothed conditional min-entropy in the i.i.d. setting remains an open question. Here we establish the second-order term in the expansion for pure states, and find that it differs from that of the original “globally” smoothed conditional min-entropy. Remarkably, this reveals that the second-order term is not uniform across states, since for other classes of states the second-order terms for partially and globally smoothed quantities coincide. In view of the tight bounds on the entanglement cost of state merging in terms of the partially-smoothed conditional min-entropy by Anshu et al., this indicates that the second-order asymptotic rate for that task will not separate so neatly into a term depending on the state (the variance) and a term depending on the error (the quantile). Finally, by relating the task of quantum compression to that of quantum state merging, our derived ex- pansion allows us to determine the second-order asymptotic expansion of the optimal rate of quantum data compression. This closes a gap in the bounds determined by Datta and Leditzky [IEEE Trans. Inf. Theory 61, 582 (2015)], and shows that the straightforward compression protocol of cutting off the eigenspace of least weight is indeed asymptotically optimal at second order.

The strong exponential-time hypothesis (SETH) is a commonly used conjecture in the field of complexity theory. It states that CNF formulas cannot be analyzed for satisfiability with a speedup over exhaustive search. This hypothesis and its variants gave rise to a fruitful field of research, fine-grained complexity, obtaining (mostly tight) lower bounds for many problems in P whose unconditional lower bounds are hard to find. In this work, we introduce a framework of Quantum Strong Exponential-Time Hypotheses, as quantum analogues to SETH. Using the QSETH framework, we are able to translate quantum query lower bounds on black-box problems to conditional quantum time lower bounds for many problems in BQP. As an example, we illustrate the use of the QSETH by providing a conditional quantum time lower bound of $\Omega(n^{1.5})$ for the Longest Common Subsequence and Edit Distance problems. We also show that the $n^2$ SETH-based lower bound for a recent scheme for Proofs of Useful Work, based on the Orthogonal Vectors problem, holds for quantum computation assuming QSETH, maintaining a quadratic gap between verifier and prover.

The closest pair problem is a fundamental problem of computational geometry: given a set of $n$ points in a $d$-dimensional space, find a pair with the smallest distance. A classical algorithm taught in introductory courses solves this problem in $O(n\log n)$ time in constant dimensions (i.e., when $d=O(1)$). This paper asks and answers the question of the problem’s quantum {time} complexity. Specifically, we give an $\tilde{O}(n^{2/3})$ algorithm in constant dimensions, which is optimal up to a polylogarithmic factor by the lower bound on the quantum query complexity of element distinctness. The key to our algorithm is an efficient history-independent data structure that supports quantum interference. In $\text{polylog}(n)$ dimensions, no known quantum algorithms perform better than brute force search, with a quadratic speedup provided by Grover’s algorithm. To give evidence that the quadratic speedup is nearly optimal, we initiate the study of quantum fine-grained complexity and introduce the \emph{Quantum Strong Exponential Time Hypothesis (QSETH)}, which is based on the assumption that Grover’s algorithm is optimal for \textsf{CNF-SAT} when the clause width is large. We show that the na\”{i}ve Grover approach to closest pair in higher dimensions is optimal up to an $n^{o(1)}$ factor unless QSETH is false. We also study the bichromatic closest pair problem and the orthogonal vectors problem, with broadly similar results.

An open problem that is widely regarded as one of the most important in quantum query complexity is to resolve the quantum query complexity of the k-distinctness function on inputs of size N. While the case of k=2 (also called Element Distinctness) is well-understood, there is a polynomial gap between the known upper and lower bounds for all constants k>2. Specifically, the best known upper bound is O(N^{(3/4)-1/(2^{k+2}-4)}) (Belovs, FOCS 2012), while the best known lower bound for k >= 2 is Omega(N^{2/3} + N^{(3/4)-1/(2k)}) (Aaronson and Shi, J.~ACM 2004; Bun, Kothari, and Thaler, STOC 2018). For any constant k >= 4, we improve the lower bound to Omega(N^{(3/4)-1/(4k)}). This yields, for example, the first proof that 4-distinctness is strictly harder than Element Distinctness. Our lower bound applies more generally to approximate degree. As a secondary result, we give a simple construction of an approximating polynomial of degree O(N^{3/4}) that applies whenever k <= polylog(N).

The quantum capacity of a noisy quantum channel determines the maximal rate at which we can code reliably over asymptotically many uses of the channel, and it characterizes the channel’s ultimate ability to transmit quantum information coherently. In this paper, we derive single-letter upper bounds on the quantum and private capacities of quantum channels. The quantum capacity of a quantum channel is always no larger than the quantum capacity of its extended channels, since the extensions of the channel can be considered as assistance from the environment. By optimizing the parametrized extended channels with specific structures such as the flag structure, we obtain new upper bounds on the quantum capacity of the original quantum channel. Furthermore, we extend our approach to estimating the fundamental limits of private communication and one-way entanglement distillation. As notable applications, we establish improved upper bounds to the quantum and private capacities for fundamental quantum channels of great interest in quantum information, some of which are also the sources of noise in superconducting quantum computing. In particular, our upper bounds on the quantum capacities of the depolarizing channel and the generalized amplitude damping channel are strictly better than previously best-known bounds.

Oblivious transfer is a cryptographic primitive where Alice has two bits and Bob wishes to learn some function of them. Ideally, Alice should not learn Bob’s desired function choice and Bob should not learn any more than logically implied by the function value. While decent quantum protocols for this task are known, many quickly become insecure if an adversary were to control the quantum devices used in the implementation of the protocol. Here we present how some existing protocols fail in this device-independent framework, and give a fully-device independent quantum protocol for XOR oblivious transfer which is provably more secure than any classical protocol.

Mixing (or quasirandom) properties of the natural transition matrix associated to a graph can be quantified by its distance to the complete graph. Different mixing properties correspond to different norms to measure this distance. For dense graphs, two such properties known as spectral expansion and uniformity were shown to be equivalent in seminal 1989 work of Chung, Graham and Wilson. Recently, Conlon and Zhao extended this equivalence to the case of sparse vertex transitive graphs using the famous Grothendieck inequality. Here we generalize these results to the non-commutative, or ‘quantum’, case, where a transition matrix becomes a quantum channel. In particular, we show that for irreducibly covariant quantum channels, expansion is equivalent to a natural analog of uniformity for graphs, generalizing the result of Conlon and Zhao. Moreover, we show that in these results, the non-commutative and commutative (resp.) Grothendieck inequalities yield the best-possible constants.

Various quantum analogues of the central limit theorem, which is one of the cornerstones of probability theory, are known in the literature. One such analogue, due to Cushen and Hudson, is of particular relevance for quantum optics. It implies that the state in any single output arm of an $n$-splitter, which is fed with $n$ copies of a centred state $\rho$ with finite second moments, converges to the Gaussian state with the same first and second moments as $\rho$. Here we exploit the phase space formalism to carry out a refined analysis of the rate of convergence in this quantum central limit theorem. For instance, we prove that the convergence takes place at a rate $\mathcal{O}\left(n^{-1/2}\right)$ in the Hilbert–Schmidt norm whenever the third moments of $\rho$ are finite. Trace norm or relative entropy bounds can be obtained by leveraging the energy boundedness of the state. Via analytical and numerical examples we show that our results are tight in many respects. An extension of our proof techniques to the non-i.i.d.\ setting is used to analyse a new model of a lossy optical fibre, where a given $m$-mode state enters a cascade of $n$ beam splitters of equal transmissivities $\lambda^{1/n}$ fed with an arbitrary (but fixed) environment state. Assuming that the latter has finite third moments, and ignoring unitaries, we show that the effective channel converges in diamond norm to a simple thermal attenuator, with a rate $\mathcal{O}\Big(n^{-\frac{1}{2(m+1)}}\Big)$. This allows us to establish bounds on the classical and quantum capacities of the cascade channel. Along the way, we derive several results that may be of independent interest. For example, we prove that any quantum characteristic function $\chi_\rho$ is uniformly bounded by some $\eta_\rho<1$ outside of any neighbourhood of the origin; also, $\eta_\rho$ can be made to depend only on the energy of the state $\rho$.

xtendibility of bosonic Gaussian states is a key issue in continuous-variable quantum information. We show that a bosonic Gaussian state is $k$-extendible if and only if it has a Gaussian $k$-extension, and we derive a simple semidefinite program, whose size scales linearly with the number of local modes, to efficiently decide $k$-extendibility of any given bosonic Gaussian state. When the system to be extended comprises one mode only, we provide a closed-form solution. Implications of these results for the steerability of quantum states and for the extendibility of bosonic Gaussian channels are discussed. We then derive upper bounds on the distance of a $k$-extendible bosonic Gaussian state to the set of all separable states, in terms of trace norm and R\’enyi relative entropies. These bounds, which can be seen as “Gaussian de Finetti theorems,” exhibit a universal scaling in the total number of modes, independently of the mean energy of the state. Finally, we establish an upper bound on the entanglement of formation of Gaussian $k$-extendible states, which has no analogue in the finite-dimensional setting.

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. The class of relaxations for combinatorial optimization has so far eluded quantum speedups. Our methods combine ideas from quantum Gibbs sampling and matrix exponent updates. A de-quantization of the algorithm also leads to a faster classical solver. For generic instances, our quantum solver gives a nearly quadratic speedup over state-of-the-art algorithms. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into constant factor approximations of the original quadratic optimization problem.

This paper considers the triangle finding problem in the CONGEST model of distributed computing. Recent works by Izumi and Le Gall (PODC’17), Chang, Pettie and Zhang (SODA’19) and Chang and Saranurak (PODC’19) have successively reduced the classical round complexity of triangle finding (as well as triangle listing) from the trivial upper bound $O(n)$ to $\tilde O(n^{1/3})$, where~$n$ denotes the number of vertices in the graph. In this paper we present a quantum distributed algorithm that solves the triangle finding problem in $\tilde O(n^{1/4})$ rounds in the CONGEST model. This gives another example of quantum algorithm beating the best known classical algorithms in distributed computing. Our result also exhibits an interesting phenomenon: while in the classical setting the best known upper bounds for the triangle finding and listing problems are identical, in the quantum setting the round complexities of these two problems are now $\tilde O(n^{1/4})$ and $\tilde \Theta(n^{1/3})$, respectively. Our result thus shows that triangle finding is easier than triangle listing in the quantum CONGEST model.

We study different decompositions of positive semidefinite matrices and nonnegative tensors and examine their approximate ranks. For any rank and norm, we define an epsilon rank as the minimum rank of an element which is epsilon close to the original element with respect to the given norm. We prove that the separations between these ranks disappear for a large class of Schatten p-norms and all entrywise p-norms with p > 1. For the trace norm (i.e. p = 1), we obtain a dependence on the ambient dimension. Our main tool is an approximate version of Caratheodory’s Theorem. We also present a deterministic algorithm to find an approximate decomposition. This work implies that it must be possible to purify states approximately at a fixed cost, which shows that the positivity problem disappears in this case.

In this work we revisit the Boolean Hidden Matching communication problem, which was the first communication problem in the one-way model to demonstrate an exponential classical-quantum communication separation. In this problem, Alice’s bits are matched into pairs according to a partition that Bob holds. These pairs are compressed using a Parity function and it is promised that the final bit-string is equal either to another bit-string Bob holds, or its complement. The problem is to decide which case is the correct one. Here we generalize the Boolean Hidden Matching problem by replacing the parity function with an arbitrary function $f$. Efficient communication protocols are presented depending on the sign-degree of $f$. If its sign-degree is less than or equal to 1, we show an efficient classical protocol. If its sign-degree is less than or equal to $2$, we show an efficient quantum protocol. We then completely characterize the classical hardness of all symmetric functions $f$ of sign-degree greater than or equal to $2$, except for one family of specific cases. We also prove, via Fourier analysis, a classical lower bound for any function $f$ whose pure high degree is greater than or equal to $2$. Similarly, we prove, also via Fourier analysis, a quantum lower bound for any function $f$ whose pure high degree is greater than or equal to $3$. These results give a large family of new exponential classical-quantum communication separations.

Many quantum information protocols require the implementation of random unitaries. Because it takes exponential resources to produce Haar-random unitaries drawn from the full n-qubit group, one often resorts to t-designs. Unitary t-designs mimic Haar-randomness up to t-th moments. It is known that Clifford operations can implement at most unitary 3-designs. In this work, we quantify the non-Clifford resources required to break this barrier. Exploiting a recently developed variant of Schur-Weyl duality for the Clifford group, wefind that it suffices to inject $O(t^4*\log^2(t), \log(1/\varepsilon))$ non-Clifford gates into a polynomial depth random Clifford circuit to obtain an ε-approximate t-design. Strikingly, the number n of qubits does not enter – asymptotically, the density of non-Clifford gates is allowed to tend to zero. As an auxiliary result that might be of independent interest, we obtain explicit bounds on the convergence time of random Clifford circuits to the t-th moment of the uniform distribution on the Clifford group.

Random quantum circuits are proficient information scramblers and efficient generators of randomness, rapidly approximating moments of the unitary group. We study the convergence of local random quantum circuits to unitary k-designs. Employing a statistical mechanical mapping, we give an exact expression of the distance to forming an approximate design as a lattice partition function. In the statistical mechanics model, the approach to randomness has a simple interpretation in terms of domain walls extending through the circuit. We analytically compute the second moment, showing that random circuits acting on n qudits form approximate 2-designs in O(n) depth, as is known. Furthermore, we argue that random circuits form approximate unitary k-designs in O(nk) depth and are thus essentially optimal in both n and k. We can show this in the limit of large local dimension, but more generally rely on a conjecture about the dominance of certain domain wall configurations.

The concept of quantum complexity has far-reaching implications spanning theoretical computer science, quantum many-body physics, and high energy physics. The quantum complexity of a unitary transformation or quantum state is defined as the size of the shortest quantum computation that executes the unitary or prepares the state. It is reasonable to expect that the complexity of a quantum state governed by a chaotic many-body Hamiltonian grows linearly with time for a time that is exponential in the system size; however, because it is hard to rule out a short-cut that improves the efficiency of a computation, it is notoriously difficult to derive lower bounds on quantum complexity for particular unitaries or states without making additional assumptions. To go further, one may study more generic models of complexity growth. We provide a rigorous connection between complexity growth and unitary k-designs, ensembles which capture the randomness of the unitary group. This connection allows us to leverage existing results about design growth to draw conclusions about the growth of complexity. We prove that local random quantum circuits generate unitary transformations whose complexity grows linearly for a long time, mirroring the behavior one expects in chaotic quantum systems and verifying conjectures by Brown and Susskind. Moreover, our results apply under a strong definition of quantum complexity based on optimal distinguishing measurements.