Affiliations: Claude Bernard University of Lyon 1 | University of Copenhagen

Extended abstract

Abstract
Designing encoding and decoding circuits to reliably send messages over many uses of a noisy channel is a central problem in communication theory. When studying the optimal transmission rates achievable with asymptotically vanishing error it is usually assumed that these circuits can be implemented using noise-free gates. While this assumption is satisfied for classical machines in many scenarios, it is not expected to be satisfied in the near term future for quantum machines where decoherence leads to faults in the quantum gates. As a result, fundamental questions regarding the practical relevance of quantum channel coding remain open. By combining techniques from fault-tolerant quantum computation with techniques from quantum communication, we initiate the study of these questions. We introduce fault-tolerant versions of quantum capacities quantifying the optimal communication rates achievable with asymptotically vanishing total error when the encoding and decoding circuits are affected by gate errors with small probability. Our main results are threshold theorems for the classical and quantum capacity: For every quantum channel $T$ and every $\epsilon>0$ there exists a threshold $p(\epsilon,T)$ for the gate error probability below which rates larger than $C-\epsilon$ are fault-tolerantly achievable with vanishing overall communication error, where $C$ denotes the usual capacity. Our results are not only relevant in communication over large distances, but also on-chip, where distant parts of a quantum computer might need to communicate under higher levels of noise than affecting the local gates.

Affiliations: Stanford University | Stanford University

Extended abstract

Abstract
In a quantum measurement process, classical information about the measured system spreads throughout the environment. Meanwhile, quantum information about the system becomes inaccessible to local observers. Here we prove a result about quantum channels indicating that an aspect of this phenomenon is completely general. We show that for any evolution of the system and environment, for everywhere in the environment excluding an O(1)-sized region we call the "quantum Markov blanket," any locally accessible information about the system must be approximately classical, i.e. obtainable from some fixed measurement. The result strengthens the earlier result of arXiv:1310.8640 in which the excluded region was allowed to grow with total environment size. It may also be seen as a new consequence of the principles of no-cloning or monogamy of entanglement. Our proof offers a constructive optimization procedure for determining the "quantum Markov blanket" region, as well as the effective measurement induced by the evolution. Alternatively, under channel-state duality, our result characterizes the marginals of multipartite states.

Affiliations: QuICS/University of Maryland | QuICS/JQI/University of Maryland | QuICS/JQI/University of Maryland | University of Colorado Boulder | Joint Quantum Institute (JQI)

Abstract
We present an optimal protocol for encoding an unknown qubit state into a multiqubit Greenberger-Horne-Zeilinger-like state and, consequently, transferring quantum information in large systems exhibiting power-law ($1/r^\alpha$) interactions. For all power-law exponents $\alpha$ between $d$ and $2d+1$, where $d$ is the dimension of the system, the protocol yields a polynomial speedup for $\alpha>2d$ and a superpolynomial speedup for $\alpha\leq 2d$, compared to the state of the art. For all $\alpha>d$, the protocol saturates the Lieb-Robinson bounds (up to subpolynomial corrections), thereby establishing the optimality of the protocol and the tightness of the bounds in this regime. The protocol has a wide range of applications, including in quantum sensing, quantum computing, and preparation of topologically ordered states.

Affiliations: QuICS | UC Santa Barbara | Weizmann Institute of Science | QuSoft, University of Amsterdam | MIT | QuSoft, University of Amsterdam

Extended abstract

Abstract
In quantum copy-protection, an adversary who is given a quantum state computing a function f cannot produce two (possibly entangled) quantum states that each individually compute f. No constructions for copy-protection are known in the plain model. We consider a weaker notion, secure software leasing (SSL), where it is only impossible to produce two copies that can both compute f using the honest evaluation algorithm. We show the following: (1) SSL is possible for a subclass of evasive functions, assuming the existence of post-quantum indistinguishability obfuscators and hardness of LWE; (2) SSL is impossible in general, assuming hardness of LWE. The second statement has important implications for existing quantum-cryptographic notions: in particular, it implies the impossibility of quantum copy-protection for arbitrary unlearnable functions, and impossibility of quantum virtual-black-box obfuscation of classical circuits.

Affiliations: LIP6, CNRS/Sorbonne Université | University of Washington | Portland State University | MIT // UC Berkeley | UC Berkeley | University of Illinois, Urbana Champaign | Princeton University and NTT Research

Extended abstract

Abstract
MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer (OT) protocol in MiniQCrypt that achieves simulation-security against malicious quantum polynomial-time adversaries, building on the foundational work of Bennett, Brassard, Crépeau and Skubiszewska (CRYPTO 1991). Combining the OT protocol with prior works, we obtain secure two-party and multi-party computation protocols also in MiniQCrypt. This is in contrast to the classical world, where it is widely believed that one-way functions alone do not give us OT.

Affiliations: Professor of Mathematics and Computer Science, UC Davis, USA

Extended abstract

Abstract
We consider the hidden subgroup problem (HSP) for infinite groups, beyond the celebrated original cases established by Shor and Kitaev. We prove that HSP is NP-hard in the rational numbers ℚ under addition, as well as for normal subgroups of a non-abelian free group F_k. We can show that HSP in the lattice ℤ^k is uSVP-hard with unary encoding of vectors. On the other hand, HSP in ℤ^k with standard binary encoding of vectors can be solved in BQP, uniformly in the dimension, generalizing the Shor-Kitaev algorithm to infinite-index hidden subgroups. HSP in any fixed, finitely generated, virtually abelian subgroup can also be solved in subexponential time using established quantum algorithms for the abelian hidden shift problem.

Affiliations: Tsinghua University | University of Maryland | Massachusetts Institute of Technology

Extended abstract

Abstract
We initiate the study of quantum algorithms for escaping from saddle points with provable guarantee. Given a function $f:\R^{n}\to\R$, our quantum algorithm outputs an $\epsilon$-approximate local minimum using $\tilde{O}(\log^{2} n/\epsilon^{1.75})$ queries to the quantum evaluation oracle (i.e., the zeroth-order oracle). Compared to the classical state-of-the-art algorithm by Jin et al.~with $\tilde{O}(\log^{6} n/\epsilon^{1.75})$ queries to the gradient oracle (i.e., the first-order oracle), our quantum algorithm is polynomially better in terms of $n$ and matches its complexity in terms of $1/\epsilon$. Our quantum algorithm is built upon two techniques: First, we replace the classical perturbations in gradient descent methods by simulating quantum wave equations, which constitutes the polynomial speedup in $n$ for escaping from saddle points. Second, we show how to use a quantum gradient computation algorithm due to Jordan to replace the classical gradient queries in nonconvex optimization by quantum evaluation queries with the same complexity, extending the same result from convex optimization due to van Apeldoorn et al. and Chakrabarti et al. Finally, we also perform numerical experiments that support our quantum speedup.

Affiliations: University of Chicago | University of Chicago // Princeton University | Princeton University | Princeton University

Extended abstract

Abstract
A foundational result in the theory of quantum computation, known as the ``principle of safe storage,'' shows that it is always possible to take a quantum circuit and produce an equivalent circuit that makes all measurements at the end of the computation. While this procedure is time efficient, meaning that it does not introduce a large overhead in the number of gates, it uses extra ancillary qubits, and so is not generally space efficient. It is quite natural to ask whether it is possible to eliminate intermediate measurements without increasing the number of ancillary qubits. We give an affirmative answer to this question by exhibiting a procedure to eliminate all intermediate measurements that is simultaneously space efficient and time efficient. In particular, this shows that the definition of a space-bounded quantum complexity class is robust to allowing or forbidding intermediate measurements. A key component of our approach, which may be of independent interest, involves showing that the well-conditioned versions of many standard linear-algebraic problems may be solved by a quantum computer in less space than seems possible by a classical computer. // We give a quantum logspace algorithm for powering contraction matrices, that is, matrices with spectral norm at most 1. The algorithm gets as an input an arbitrary $n\times n$ contraction matrix $A$, and a parameter $T \leq \mathrm{poly}(n)$ and outputs the entries of $A^T$, up to (arbitrary) polynomially small additive error. The algorithm applies only unitary operators, without intermediate measurements. We show various implications and applications of this result: First, we use this algorithm to show that the class of quantum logspace algorithms with only quantum memory and with intermediate measurements is equivalent to the class of quantum logspace algorithms with only quantum memory without intermediate measurements. This shows that the deferred-measurement principle, a fundamental principle of quantum computing, applies also for quantum logspace algorithms (without classical memory). More generally, we give a quantum algorithm with space $O(S + \log T)$ that takes as an input the description of a quantum algorithm with quantum space $S$ and time $T$, with intermediate measurements (without classical memory), and simulates it unitarily with polynomially small error, without intermediate measurements. Since unitary transformations are reversible (while measurements are irreversible) an interesting aspect of this result is that it shows that any quantum logspace algorithm (without classical memory) can be simulated by a reversible quantum logspace algorithm. This proves a quantum analogue of the result of Lange, McKenzie and Tapp that deterministic logspace is equal to reversible logspace. Finally, we use our results to show non-trivial classical simulations of quantum logspace learning algorithms.

Affiliations: AWS Center for Quantum Computing | Faculty of Physics, University of Warsaw

Abstract
We present a simple proof of the approximate Eastin-Knill theorem, which connects the quality of a quantum error-correcting code (QECC) with its ability to achieve a universal set of transversal logical gates. Our derivation employs powerful bounds on the quantum Fisher information in generic quantum metrological protocols to characterize the QECC performance measured in terms of the worst-case entanglement fidelity. The theorem is applicable to a large class of decoherence models, including erasure and depolarizing noise. Our approach is unorthodox, as instead of following the established path of utilizing QECCs to mitigate noise in quantum metrological protocols, we apply methods of quantum metrology to explore the limitations of QECCs.

Affiliations: University College London | University College London

Abstract
We introduce a technique that uses gauge fixing to significantly improve the quantum error correcting performance of subsystem codes. By changing the order in which check operators are measured, valuable additional information can be gained, and we introduce a new method for decoding which uses this information to improve performance. Applied to the subsystem toric code with three-qubit check operators, we increase the threshold under circuit-level depolarising noise from 0.67% to 0.81%. The threshold increases further under a circuit-level noise model with small finite bias, up to 2.22% for infinite bias. Furthermore, we construct families of finite-rate subsystem LDPC codes with three-qubit check operators and optimal-depth parity-check measurement schedules. To the best of our knowledge, these finite-rate subsystem codes outperform all known codes at circuit-level depolarising error rates as high as 0.2%, where they have a qubit overhead that is 4.3× lower than the most efficient version of the surface code and 5.1× lower than the subsystem toric code. Their threshold and pseudo-threshold exceeds 0.42% for circuit-level depolarising noise, increasing to 2.4% under infinite bias using gauge fixing.

Affiliations: Los Alamos National Laboratory | Los Alamos National Laboratory

Extended abstract

Abstract
We study the problem of simulating the dynamics of spin systems when the initial state is supported on a subspace of low energy of a Hamiltonian $H$. This is a central problem in physics with vast applications in many-body systems and beyond, where the interesting physics takes place in the low-energy sector. We analyze error bounds induced by product formulas that approximate the evolution operator and show that these bounds depend on an effective low-energy norm of $H$. We find improvements over the best previous complexities of product formulas that apply to the general case, and these improvements are more significant for long evolution times that scale with the system size and/or small approximation errors. To obtain these improvements, we prove novel exponentially-decaying upper bounds on the leakage to high-energy subspaces due to the product formula. Our results provide a path to a systematic study of Hamiltonian simulation at low energies, which will be required to push quantum simulation closer to reality.

Affiliations: Institute for Quantum Computing, University of Waterloo ; Perimeter Institute | Jagiellonian University | Jagiellonian University | The University of Sydney

Extended abstract

Abstract
We present two classical algorithms for the simulation of universal quantum circuits on n qubits constructed from c instances of Clifford gates and t arbitrary-angle Z-rotation gates such as T gates. Our algorithms complement each other by performing best in different parameter regimes. The Estimate algorithm produces an additive precision estimate of the Born rule probability of a chosen measurement outcome with the only source of run-time inefficiency being a linear dependence on the stabilizer extent (which scales like ≈1.17^t for T gates). Our algorithm is state-of-the-art for this task: as an example, in approximately 25 hours (on a standard desktop computer), we estimated the Born rule probability to within an additive error of 0.03, for a 50 qubit, 60 non-Clifford gate quantum circuit with more than 2000 Clifford gates. The Compute algorithm calculates the probability of a chosen measurement outcome to machine precision with run-time O(2^(t−r) (t−r)t) where r is an efficiently computable, circuit-specific quantity. With high probability, r is very close to min{t,n−w} for random circuits with many Clifford gates, where w is the number of measured qubits. Compute can be effective in surprisingly challenging parameter regimes, e.g., we can randomly sample Clifford+T circuits with n=55, w=5, c=10^5 and t=80 T-gates, and then compute the Born rule probability with a run-time consistently less than 104 seconds using a single core of a standard desktop computer. We provide a C+Python implementation of our algorithms.

Affiliations: University of Maryland Computer Science/NIST | University of Maryland Mathematics

Extended abstract

Abstract
We present a classical algorithm that, for any geometrically-local, constant-depth quantum circuit $C$, and any bit string $x \in \{0,1\}^n$, can compute the quantity $|\bra{0^{\otimes n}}C \ket{x}|^2$ to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is $\#P$-hard to compute this same quantity to within $2^{-n^2}$ additive error \cite{Mov19}. The previous best known algorithm for this problem used $O(2^{n^{1/3}}\poly(1/\epsilon))$ time to compute probabilities to within additive error $\epsilon$ \cite{BGM19}. Notably, the \cite{BGM19} paper included an elegant polynomial time algorithm for the same estimation task with 2D circuits, which makes a novel use of 1D Matrix Product States carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach: Constructing a recursive sub-division of the given 3D circuit using carefully designed block-encodings.