Estimating the expectation value of an operator corresponding to an observable is a fundamental task in quantum computation. It is often impossible to obtain such estimates directly, as the computer is restricted to measuring in a fixed computational basis. One common solution splits the operator into a weighted sum of Pauli operators and measures each separately, at the cost of many measurements. An improved version collects mutually commuting Pauli operators together before measuring all operators within a collection simultaneously. The effectiveness of doing this depends on two factors. Firstly, we must understand the improvement offered by a given arrangement of Paulis in collections. In our work, we propose two natural metrics for quantifying this, operating under the assumption that measurements are distributed optimally among collections so as to minimise the overall finite sampling error. Motivated by the mathematical form of these metrics, we introduce SORTED INSERTION, a collecting strategy that exploits the weighting of each Pauli operator in the overall sum. Secondly, to measure all Pauli operators within a collection simultaneously, a circuit is required to rotate them to the computational basis. In our work, we present two efficient circuit constructions that suitably rotate any collection of $k$ independent commuting $n$-qubit Pauli operators using at most $kn-k(k+1)/2$ and $O(kn/\log k)$ two-qubit gates respectively. Our methods are numerically illustrated in the context of the Variational Quantum Eigensolver, where the operators in question are molecular Hamiltonians. As measured by our metrics, SORTED INSERTION outperforms four conventional greedy colouring algorithms that seek the minimum number of collections.
Kliuchnikov, Maslov, and Mosca proved in 2012 that a $2\times 2$ unitary matrix $V$ can be exactly represented by a single-qubit Clifford+$T$ circuit if and only if the entries of $V$ belong to the ring $\mathbb{Z}[1/\sqrt{2},i]$. Later that year, Giles and Selinger showed that the same restriction applies to matrices that can be exactly represented by a multi-qubit Clifford+$T$ circuit. These number-theoretic characterizations shed new light upon the structure of Clifford+$T$ circuits and led to remarkable developments in the field of quantum compiling. In the present paper, we provide number-theoretic characterizations for certain restricted Clifford+$T$ circuits by considering unitary matrices over subrings of $\mathbb{Z}[1/\sqrt{2},i]$. We focus on the subrings $\mathbb{Z}[1/2]$, $\mathbb{Z}[1/\sqrt{2}]$, $\mathbb{Z}[1/i\sqrt{2}]$, and $\mathbb{Z}[1/2,i]$, and we prove that unitary matrices with entries in these rings correspond to circuits over well-known universal gate sets. In each case, the desired gate set is obtained by extending the set of classical reversible gates $\{X, CX, CCX\}$ with an analogue of the Hadamard gate and an optional phase gate.
To what extent does Noether's principle apply to quantum channels? Here, we quantify the degree to which imposing a symmetry constraint on quantum channels implies a conservation law, and show that this relates to physically impossible transformations in quantum theory, such as time-reversal and spin-inversion. In this analysis, the convex structure and extremal points of the set of quantum channels symmetric under the action of a Lie group $G$ becomes essential. It allows us to derive bounds on the deviation from conservation laws under any symmetric quantum channel in terms of the deviation from closed dynamics as measured by the unitarity of the channel. In particular, we investigate in detail the $U(1)$ and $SU(2)$ symmetries related to energy and angular momentum conservation laws. In the latter case, we provide fundamental limits on how much a spin-$j_A$ system can be used to polarise a larger spin-$j_B$ system, and on how much one can invert spin polarisation using a rotationally-symmetric operation. Finally, we also establish novel links between unitarity, complementary channels and purity that are of independent interest.
Tensor-network techniques have enjoyed outstanding success in physics, and have recently attracted attention in machine learning, both as a tool for the formulation of new learning algorithms and for enhancing the mathematical understanding of existing methods. Inspired by these developments, and the natural correspondence between tensor networks and probabilistic graphical models, we provide a rigorous analysis of the expressive power of various tensor-network factorizations of discrete multivariate probability distributions. These factorizations include non-negative tensor-trains/MPS, which are in correspondence with hidden Markov models, and Born machines, which are naturally related to local quantum circuits. When used to model probability distributions, they exhibit tractable likelihoods and admit efficient learning algorithms. Interestingly, we prove that there exist probability distributions for which there are unbounded separations between the resource requirements of some of these tensor-network factorizations. Particularly surprising is the fact that using complex instead of real tensors can lead to an arbitrarily large reduction in the number of parameters of the network. Additionally, we introduce locally purified states (LPS), a new factorization inspired by techniques for the simulation of quantum systems, with provably better expressive power than all other representations considered. The ramifications of this result are explored through numerical experiments. Our findings imply that LPS should be considered over hidden Markov models, and furthermore provide guidelines for the design of local quantum circuits for probabilistic modeling.
Recently, Bravyi, Gosset, and König (Science, 2018) exhibited a search problem called the 2D Hidden Linear Function (2D HLF) problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (or QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (or NC^0 circuits). In other words, they exhibited a search problem in QNC^0 that is not in NC^0. We strengthen their result by proving that the 2D HLF problem is not contained in AC^0, the class of classical, polynomial-size, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates. We also supplement this worst-case lower bound with an average-case result: There exists a simple distribution under which any AC^0 circuit (even of nearly exponential size) has exponentially small correlation with the 2D HLF problem. Our results are shown by constructing a new problem in QNC^0, which we call the Relaxed Parity Halving Problem, which is easier to work with. We prove our AC^0 lower bounds for this problem, and then show that it reduces to the 2D HLF problem. As a step towards even stronger lower bounds, we present a search problem that we call the Parity Bending Problem, which is in QNC^0/qpoly (QNC^0 circuits that are allowed to start with a quantum state of their choice that is independent of the input), but is not even in AC^0[2] (the class AC^0 with unbounded fan-in XOR gates). All the quantum circuits in our paper are simple, and the main difficulty lies in proving the classical lower bounds. For this we employ a host of techniques, including a refinement of Håstad's switching lemmas for multi-output circuits that may be of independent interest, the Razborov-Smolensky AC^0[2] lower bound, Vazirani's XOR lemma, and lower bounds for non-local games.
The theory of quantum thermodynamics investigates how the concepts of heat, work, and temperature can be carried over to the quantum realm, where fluctuations and randomness are fundamentally unavoidable. Of particular practical relevance is the investigation of quantum thermal machines: Machines that use the flow of heat in order to perform some useful task. In this lectures series, we give a brief introduction into how the laws of thermodynamics arise from quantum theory and how thermal machines can be described with Markovian quantum master equations. Recent results are illustrated with examples such as a quantum dot heat engine and a qubit entangler.
Hybrid quantum-classical systems make it possible to utilize existing quantum computers to their fullest extent. Within this framework, parameterized quantum circuits can be regarded as machine learning models with remarkable expressive power. This Review presents the components of these models and discusses their application to a variety of data-driven tasks, such as supervised learning and generative modeling. With an increasing number of experimental demonstrations carried out on actual quantum hardware and with software being actively developed, this rapidly growing field is poised to have a broad spectrum of real-world applications.
The real-time flux dynamics of up to three superconducting quantum interference devices (SQUIDs) are studied by numerically solving the time-dependent Schrödinger equation. The numerical results are used to scrutinize the mapping of the flux degrees of freedom onto two-level systems (the qubits) as well as the performance of the intermediate SQUID as a tunable coupling element. It is shown that the qubit representation yields a good description of the flux dynamics during quantum annealing and the presence of the tunable coupling element does not have negative effects on the overall performance. Additionally, data obtained from a simulation of the dynamics of two-level systems during quantum annealing are compared to experimental data produced by the D-Wave 2000Q quantum annealer. The effects of finite temperature are incorporated in the simulation by coupling the qubit system to a bath of two-level systems. It is shown that an environment modeled as non-interacting two-level systems coupled to the qubits can produce data which matches the experimental data much better than the simulation data of the qubits without coupling to an environment and better than data obtained from a simulation of an environment modeled as interacting two-level systems coupling to the qubits.
We analyse quasi-periodically driven quantum systems that can be mapped exactly to periodically driven ones and find Floquet Time Spirals in analogy with spatially incommensurate spiral magnetic states. Generalising the mechanism to many-body systems we discover that a form of discrete time-translation symmetry breaking can also occur in quasi-periodically driven systems. We construct a discrete time quasi-crystal stabilised by many-body localisation. Crucially, it persists also under perturbations that break the equivalence with periodic systems. As such it provides evidence of a stable quasi-periodically driven many-body quantum system which does not heat up to the featureless infinite temperature state.
Based on his extension of the classical argument of Einstein, Podolsky and Rosen, Schrödinger observed that, in certain quantum states associated with pairs of particles that can be far away from one another, the result of the measurement of an observable associated with one particle is perfectly correlated with the result of the measurement of another observable associated with the other particle. Combining this with the assumption of locality and some "no hidden variables" theorems, we showed in a previous paper [11] that this yields a contradiction. This means that the assumption of locality is false, and thus provides us with another demonstration of quantum nonlocality that does not involve Bell's (or any other) inequalities. In [11] we introduced only "spin-like" observables acting on finite dimensional Hilbert spaces. Here we will give a similar argument using the variables originally used by Einstein, Podolsky and Rosen, namely position and momentum.