Michal Oszmaniec

We present a classical algorithm capable of estimating Born rule probabilities of quantum circuits consisting of matchgate/Fermionic linear optical (FLO) unitaries and non-FLO controlled-phase gates with arbitrary phases. Our algorithm has asymptotic runtime linear in an (in general) exponentially large quantity we have named the “FLO-extent”, and is at most polynomial all other parameters. The FLO-extent is defined in a similar way to the stabilizer extent known from the literature on quantum simulation using stabilizer decompositions. The FLO extent is sub-multiplicative, and the multiplicative upper bound leads to a runtime for our algorithm which doubles for each swap gate, or controlled-Z gate added to the circuit. Controlled-phase gates with different phases have lower extent, smoothly interpolating between 1 and 2. These numbers can be compared with the prior state of-the-art for this task, the runtime of which is multiplied by a factor 9 for each CZ-gate. This dramatic difference in performance is due to our use of methods we have developed to perform tasks in the FLO subtheory in a phase-sensitive way, allowing us to decompose the relevant “magic states” at the level of statevectors rather than density operators. Our results are formulated for quantum circuits, directly extending the class of quantum computations that can be simulated using current classical computers. However, the FLO subtheory also naturally represents the evolution of non-interacting Fermions, while the addition of non-FLO unitaries to the circuit can represent interactions between Fermions. We therefore expect that our results will be applicable to classical simulations of weakly interacting Fermions, with potential applications in condensed matter and quantum chemistry research. In addition to practical simulation our work is part of the ongoing effort to understand the differences between the computational power of classical and that of quantum mechanics. By extending classical simulation methods to new areas we can focus attention on those features of quantum computations which are necessary for meaningful "quantum advantage".

Abstract Epsilon-nets and approximate unitary t-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. The former constitute subsets of unitary channels that are epsilon-close to any unitary channel in the diamond norm. The latter are ensembles of unitaries that (approximately) recover Haar averages of polynomials in entries of unitary channels up to order t. In this work we systematically study quantitative connections between these two notions. Specifically, we prove that, for a fixed dimension d of the Hilbert space, unitaries constituting delta-approximate t-expanders form epsilon-nets for t~(d^(5/2))/epsilon and delta~[(epsilon^(3/2))/d]^(d^2). We also show that epsilon-nets can be used to construct delta-approximate unitary t-designs for delt~epsilon*t, where the notion of approximation is based on the diamond norm. Finally, we prove that the degree of an exact unitary t-design necessary to obtain an epsilon-net must grow at least fast as 1/epsilon (for fixed dimension) and not slower than d^2 (for fixed epsilon). This shows near optimality of our result connecting t-designs and epsilon-nets. We further apply our findings in conjunction with the recent results of Varju 2013 in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in Brandao-Harrow-Horodecki 2016. Importantly, our gate sets need not to be symmetric (i.e. contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider a problem of compilation of quantum gates and prove a non-constructive version of the Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.

Abstract It is imperative to minimize resources needed to implement quantum operations on existing near-term quantum devices. With this in mind, we propose a scheme to implement an arbitrary general quantum measurement, also known as Positive Operator Valued Measures (POVM) in dimension d using only classical resources and a single ancillary qubit. The proposed method is based on probabilistic implementation of d outcome measurements which is followed by postselection on some of the received outcomes. This is an extension of an earlier work which required dichotomic measurements, no additional ancillary qubits, and whose success probability scaled like 1/d. The success probability of our scheme depends on the operator norms of the coarse grained POVM effects. Significantly, we show that for typical Haar random rank-one POVMs with at most d 2 outcomes, the success probability of our simulation scheme does not go to zero with the dimension of the system. We conjecture that this is true for all POVMs in dimension d. This is supported by numerical computations showing constant success probability for SIC-POVMs and (non symmetric) IC-POVMs in dimensions up to 323. Additionally, for the gate noise model used in the recent demonstration of quantum computational advantage by Google, we prove that for typical Haar random POVMs noise compounding in circuits required by our scheme is substantially lower than in the scheme that directly uses Naimarks dilation theorem. 12:30 - 13:00 Round tables with Piotr Kopszak, Michal Studzinski, Yuxiang Yang, Tanmay Singal, and Filip Maciejewski At the end of the session, you can meet with the speakers directly. Round tables take place in parallel, each speaker having their own meeting. Session 2B Stage B