Search

We develop a framework for learning properties of quantum states beyond the assumption of independent and identically distributed (i.i.d.) input states. We prove that, given any learning problem (under reasonable assumptions), an algorithm designed for i.i.d. input states can be adapted to handle input states of any nature, albeit at the expense of a polynomial increase in copy complexity. Furthermore, we establish that algorithms which perform non-adaptive incoherent measurements can be extended to encompass non-i.i.d. input states while maintaining comparable error probabilities. This allows us, among others applications, to generalize the classical shadows of Huang, Kueng, and Preskill to the non-i.i.d. setting at the cost of a small loss in efficiency. Additionally, we can efficiently verify any pure state using Clifford measurements, in a way that is independent of the ideal state. Our main techniques are based on de Finetti-style theorems supported by tools from information theory. In particular, we prove a new randomized local de Finetti theorem that can be of independent interest.

In this work, we show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms. In particular, for brickwork random quantum circuits on $n$ qubits of depth $d$, we show three main results: - At super logarithmic circuit depth $d=\omega(\log(n))$, any learning algorithm requires super polynomially many queries to achieve a constant probability of success over the randomly drawn instance. - There exists a $d=O(n)$, such that any learning algorithm requires $\Omega(2^n)$ queries to achieve a $O(2^{-n})$ probability of success over the randomly drawn instance. - At infinite circuit depth $d\to\infty$, any learning algorithm requires $2^{2^{\Omega(n)}}$ many queries to achieve a $2^{-2^{\Omega(n)}}$ probability of success over the randomly drawn instance. As an auxiliary result of independent interest, we show that the output distribution of a brickwork random quantum circuit is constantly far from any fixed distribution in total variation distance with probability $1-O(2^{-n})$, which confirms a variant of a conjecture by Aaronson and Chen., Comment: 57 pages

Circuit synthesis is the task of decomposing a given logical functionality into a sequence of elementary gates. It is (depth-)optimal if it is impossible to achieve the desired functionality with even shorter circuits. Optimal synthesis is a central problem in both quantum and classical hardware design, but also plagued by complexity-theoretic obstacles. Motivated by fault-tolerant quantum computation, we consider the special case of synthesizing blocks of Clifford unitaries. Leveraging entangling input stimuli and the stabilizer formalism allows us to reduce the Clifford synthesis problem to a family of poly-size satisfiability (SAT) problems -- one for each target circuit depth. On a conceptual level, our result showcases that the Clifford synthesis problem is contained in the first level of the polynomial hierarchy ($\mathsf{NP}$), while the classical synthesis problem for logical circuits is known to be complete for the second level of the polynomial hierarchy ($\Sigma_2^{\mathsf{P}}$). Based on this theoretical reduction, we formulate a SAT encoding for depth-optimal Clifford synthesis. We then employ SAT solvers to determine a satisfying assignment or to prove that no such assignment exists. From that, the shortest depth for which synthesis is still possible (optimality) as well as the actual circuit (synthesis) can be obtained. Empirical evaluations show that the optimal synthesis approach yields a substantial depth improvement for random Clifford circuits and Clifford+T circuits for Grover search., Comment: 12 pages, 2 figures, 1 table, implementation publicly available at https://github.com/cda-tum/qmap

Finding the ground state of a quantum many-body system is a fundamental problem in quantum physics. In this work, we give a classical machine learning (ML) algorithm for predicting ground state properties with an inductive bias encoding geometric locality. The proposed ML model can efficiently predict ground state properties of an $n$-qubit gapped local Hamiltonian after learning from only $\mathcal{O}(\log(n))$ data about other Hamiltonians in the same quantum phase of matter. This improves substantially upon previous results that require $\mathcal{O}(n^c)$ data for a large constant $c$. Furthermore, the training and prediction time of the proposed ML model scale as $\mathcal{O}(n \log n)$ in the number of qubits $n$. Numerical experiments on physical systems with up to 45 qubits confirm the favorable scaling in predicting ground state properties using a small training dataset., Comment: 8 pages, 5 figures + 32-page appendix

The operator entanglement (OE) is a key quantifier of the complexity of a reduced density matrix. In out-of-equilibrium situations, e.g. after a quantum quench of a product state, it is expected to exhibit an entanglement barrier. The OE of a reduced density matrix initially grows linearly as entanglement builds up between the local degrees of freedom, it then reaches a maximum, and ultimately decays to a small finite value as the reduced density matrix converges to a simple stationary state through standard thermalization mechanisms. Here, by performing a new data analysis of the published experimental results of [Brydges et al., Science 364, 260 (2019)], we obtain the first experimental measurement of the OE of a subsystem reduced density matrix in a quantum many-body system. We employ the randomized measurements toolbox and we introduce and develop a new efficient method to post-process experimental data in order to extract higher-order density matrix functionals and access the OE. The OE thus obtained displays the expected barrier as long as the experimental system is large enough. For smaller systems, we observe a barrier with a double-peak structure, whose origin can be interpreted in terms of pairs of quasi-particles being reflected at the boundary of the qubit chain. As $U(1)$ symmetry plays a key role in our analysis, we introduce the notion of symmetry resolved operator entanglement (SROE), in addition to the total OE. To gain further insights into the SROE, we provide a thorough theoretical analysis of this new quantity in chains of non-interacting fermions, which, in spite of their simplicity, capture most of the main features of OE and SROE. In particular, we uncover three main physical effects: the presence of a barrier in any charge sector, a time delay for the onset of the growth of SROE, and an effective equipartition between charge sectors., Comment: 13 + 24 pages with 3 + 7 figures

The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm, where a quantum computer implements a variational ansatz consisting of $p$ layers of alternating unitary operators and a classical computer is used to optimize the variational parameters. For a random initialization, the optimization typically leads to local minima with poor performance, motivating the search for initialization strategies of QAOA variational parameters. Although numerous heuristic initializations exist, an analytical understanding and performance guarantees for large $p$ remain evasive. We introduce a greedy initialization of QAOA which guarantees improving performance with an increasing number of layers. Our main result is an analytic construction of $2p+1$ transition states - saddle points with a unique negative curvature direction - for QAOA with $p+1$ layers that use the local minimum of QAOA with $p$ layers. Transition states connect to new local minima, which are guaranteed to lower the energy compared to the minimum found for $p$ layers. We use the GREEDY procedure to navigate the exponentially increasing with $p$ number of local minima resulting from the recursive application of our analytic construction. The performance of the GREEDY procedure matches available initialization strategies while providing a guarantee for the minimal energy to decrease with an increasing number of layers $p$., Comment: 15 pages, 9 figures, updated to be close to published version

Fidelity is arguably the most popular figure of merit in quantum sciences. However, many of its properties are still unknown. In this work, we resolve the open problem of maximizing average fidelity over arbitrary finite ensembles of quantum states and derive new upper bounds. We first construct a semidefinite program whose optimal value is the maximum average fidelity and then derive fixed-point algorithms that converge to the optimal state. The fixed-point algorithms outperform the semidefinite program in terms of numerical runtime. We also derive expressions for near-optimal states that are easier to compute and upper and lower bounds for maximum average fidelity that are exact when all the states in the ensemble commute. Finally, we discuss how our results solve some open problems in Bayesian quantum tomography., Comment: 24 + 1 pages and 5 figures. Code available at https://github.com/afhamash/optimal-average-fidelity

Quantum computers solve ever more complex tasks using steadily growing system sizes. Characterizing these quantum systems is vital, yet becoming increasingly challenging. The gold-standard is quantum state tomography (QST), capable of fully reconstructing a quantum state without prior knowledge. Measurement and classical computing costs, however, increase exponentially in the system size - a bottleneck given the scale of existing and near-term quantum devices. Here, we demonstrate a scalable and practical QST approach that uses a single measurement setting, namely symmetric informationally complete (SIC) positive operator-valued measures (POVM). We implement these nonorthogonal measurements on an ion trap device by utilizing more energy levels in each ion - without ancilla qubits. More precisely, we locally map the SIC POVM to orthogonal states embedded in a higher-dimensional system, which we read out using repeated in-sequence detections, providing full tomographic information in every shot. Combining this SIC tomography with the recently developed randomized measurement toolbox ("classical shadows") proves to be a powerful combination. SIC tomography alleviates the need for choosing measurement settings at random ("derandomization"), while classical shadows enable the estimation of arbitrary polynomial functions of the density matrix orders of magnitudes faster than standard methods. The latter enables in-depth entanglement studies, which we experimentally showcase on a 5-qubit absolutely maximally entangled (AME) state. Moreover, the fact that the full tomography information is available in every shot enables online QST in real time. We demonstrate this on an 8-qubit entangled state, as well as for fast state identification. All in all, these features single out SIC-based classical shadow estimation as a highly scalable and convenient tool for quantum state characterization., Comment: 34 pages, 15 figures

Increasingly sophisticated programmable quantum simulators and quantum computers are opening unprecedented opportunities for exploring and exploiting the properties of highly entangled complex quantum systems. The complexity of large quantum systems is the source of their power, but also makes them difficult to control precisely or characterize accurately using measured classical data. We review recently developed protocols for probing the properties of complex many-qubit systems using measurement schemes that are practical using today's quantum platforms. In all these protocols, a quantum state is repeatedly prepared and measured in a randomly chosen basis; then a classical computer processes the measurement outcomes to estimate the desired property. The randomization of the measurement procedure has distinct advantages; for example, a single data set can be employed multiple times to pursue a variety of applications, and imperfections in the measurements are mapped to a simplified noise model that can more easily be mitigated. We discuss a range of use cases that have already been realized in quantum devices, including Hamiltonian simulation tasks, probes of quantum chaos, measurements of nonlocal order parameters, and comparison of quantum states produced in distantly separated laboratories. By providing a workable method for translating a complex quantum state into a succinct classical representation that preserves a rich variety of relevant physical properties, the randomized measurement toolbox strengthens our ability to grasp and control the quantum world.

Variational quantum algorithms are promising algorithms for achieving quantum advantage on near-term devices. The quantum hardware is used to implement a variational wave function and measure observables, whereas the classical computer is used to store and update the variational parameters. The optimization landscape of expressive variational ans\"atze is however dominated by large regions in parameter space, known as barren plateaus, with vanishing gradients which prevents efficient optimization. In this work we propose a general algorithm to avoid barren plateaus in the initialization and throughout the optimization. To this end we define a notion of weak barren plateaus (WBP) based on the entropies of local reduced density matrices. The presence of WBPs can be efficiently quantified using recently introduced shadow tomography of the quantum state with a classical computer. We demonstrate that avoidance of WBPs suffices to ensure sizable gradients in the initialization. In addition, we demonstrate that decreasing the gradient step size, guided by the entropies allows to avoid WBPs during the optimization process. This paves the way for efficient barren plateau free optimization on near-term devices., Comment: 9 pages, 4 figures, comments are welcome; v2: improved readability, added new section and data, added more citations

Quantum technology has the potential to revolutionize how we acquire and process experimental data to learn about the physical world. An experimental setup that transduces data from a physical system to a stable quantum memory, and processes that data using a quantum computer, could have significant advantages over conventional experiments in which the physical system is measured and the outcomes are processed using a classical computer. We prove that, in various tasks, quantum machines can learn from exponentially fewer experiments than those required in conventional experiments. The exponential advantage holds in predicting properties of physical systems, performing quantum principal component analysis on noisy states, and learning approximate models of physical dynamics. In some tasks, the quantum processing needed to achieve the exponential advantage can be modest; for example, one can simultaneously learn about many noncommuting observables by processing only two copies of the system. Conducting experiments with up to 40 superconducting qubits and 1300 quantum gates, we demonstrate that a substantial quantum advantage can be realized using today's relatively noisy quantum processors. Our results highlight how quantum technology can enable powerful new strategies to learn about nature., Comment: 6 pages, 17 figures + 46 page appendix; open-source code available at https://github.com/quantumlib/ReCirq/tree/master/recirq/qml_lfe

We propose and investigate a new method of quantum process tomography (QPT) which we call projected least squares (PLS). In short, PLS consists of first computing the least-squares estimator of the Choi matrix of an unknown channel, and subsequently projecting it onto the convex set of Choi matrices. We consider four experimental setups including direct QPT with Pauli eigenvectors as input and Pauli measurements, and ancilla-assisted QPT with mutually unbiased bases (MUB) measurements. In each case, we provide a closed form solution for the least-squares estimator of the Choi matrix. We propose a novel, two-step method for projecting these estimators onto the set of matrices representing physical quantum channels, and a fast numerical implementation in the form of the hyperplane intersection projection algorithm. We provide rigorous, non-asymptotic concentration bounds, sampling complexities and confidence regions for the Frobenius and trace-norm error of the estimators. For the Frobenius error, the bounds are linear in the rank of the Choi matrix, and for low ranks, they improve the error rates of the least squares estimator by a factor $d^2$, where $d$ is the system dimension. We illustrate the method with numerical experiments involving channels on systems with up to 7 qubits, and find that PLS has highly competitive accuracy and computational tractability., Comment: 13+9 pages, 8 figures

Classical machine learning (ML) provides a potentially powerful approach to solving challenging quantum many-body problems in physics and chemistry. However, the advantages of ML over more traditional methods have not been firmly established. In this work, we prove that classical ML algorithms can efficiently predict ground state properties of gapped Hamiltonians in finite spatial dimensions, after learning from data obtained by measuring other Hamiltonians in the same quantum phase of matter. In contrast, under widely accepted complexity theory assumptions, classical algorithms that do not learn from data cannot achieve the same guarantee. We also prove that classical ML algorithms can efficiently classify a wide range of quantum phases of matter. Our arguments are based on the concept of a classical shadow, a succinct classical description of a many-body quantum state that can be constructed in feasible quantum experiments and be used to predict many properties of the state. Extensive numerical experiments corroborate our theoretical results in a variety of scenarios, including Rydberg atom systems, 2D random Heisenberg models, symmetry-protected topological phases, and topologically ordered phases., Comment: 10 pages, 13 figures + 60-page appendix; v4: Fixed a minor formatting issue; open-source code available at https://github.com/hsinyuan-huang/provable-ml-quantum

Low-rank matrix recovery problems arise naturally as mathematical formulations of various inverse problems, such as matrix completion, blind deconvolution, and phase retrieval. Over the last two decades, a number of works have rigorously analyzed the reconstruction performance for such scenarios, giving rise to a rather general understanding of the potential and the limitations of low-rank matrix models in sensing problems. In this article, we compare the two main proof techniques that have been paving the way to a rigorous analysis, discuss their potential and limitations, and survey their successful applications. On the one hand, we review approaches based on descent cone analysis, showing that they often lead to strong guarantees even in the presence of adversarial noise, but face limitations when it comes to structured observations. On the other hand, we discuss techniques using approximate dual certificates and the golfing scheme, which are often better suited to deal with practical measurement structures, but sometimes lead to weaker guarantees. Lastly, we review recent progress towards analyzing descent cones also for structured scenarios -- exploiting the idea of splitting the cones into multiple parts that are analyzed via different techniques., Comment: 39 pages, 6 figures

Given an arbitrary matrix $A\in\mathbb{R}^{n\times n}$, we consider the fundamental problem of computing $Ax$ for any $x\in\mathbb{R}^n$ such that $Ax$ is $s$-sparse. While fast algorithms exist for particular choices of $A$, such as the discrete Fourier transform, there is currently no $o(n^2)$ algorithm that treats the unstructured case. In this paper, we devise a randomized approach to tackle the unstructured case. Our method relies on a representation of $A$ in terms of certain real-valued mutually unbiased bases derived from Kerdock sets. In the preprocessing phase of our algorithm, we compute this representation of $A$ in $O(n^3\log n)$ operations. Next, given any unit vector $x\in\mathbb{R}^n$ such that $Ax$ is $s$-sparse, our randomized fast transform uses this representation of $A$ to compute the entrywise $\epsilon$-hard threshold of $Ax$ with high probability in only $O(sn + \epsilon^{-2}\|A\|_{2\to\infty}^2n\log n)$ operations. In addition to a performance guarantee, we provide numerical results that demonstrate the plausibility of real-world implementation of our algorithm.

We propose an ordered set of experimentally accessible conditions for detecting entanglement in mixed states. The $k$-th condition involves comparing moments of the partially transposed density operator up to order $k$. Remarkably, the union of all moment inequalities reproduces the Peres-Horodecki criterion for detecting entanglement. Our empirical studies highlight that the first four conditions already detect mixed state entanglement reliably in a variety of quantum architectures. Exploiting symmetries can help to further improve their detection capabilities. We also show how to estimate moment inequalities based on local random measurements of single state copies (classical shadows) and derive statistically sound confidence intervals as a function of the number of performed measurements. Our analysis includes the experimentally relevant situation of drifting sources, i.e. non-identical, but independent, state copies., Comment: 11+11 pages, 6 figures

We consider the problem of jointly estimating expectation values of many Pauli observables, a crucial subroutine in variational quantum algorithms. Starting with randomized measurements, we propose an efficient derandomization procedure that iteratively replaces random single-qubit measurements with fixed Pauli measurements; the resulting deterministic measurement procedure is guaranteed to perform at least as well as the randomized one. In particular, for estimating any $L$ low-weight Pauli observables, a deterministic measurement on only of order $\log(L)$ copies of a quantum state suffices. In some cases, for example when some of the Pauli observables have a high weight, the derandomized procedure is substantially better than the randomized one. Specifically, numerical experiments highlight the advantages of our derandomized protocol over various previous methods for estimating the ground-state energies of small molecules., Comment: 12 pages, 2 figures, 1 table; open-source code available at https://github.com/momohuang/predicting-quantum-properties

When a quantum system initialized in a product state is subjected to either coherent or incoherent dynamics, the entropy of any of its connected partitions generically increases as a function of time, signalling the inevitable spreading of (quantum) information throughout the system. Here, we show that, in the presence of continuous symmetries and under ubiquitous experimental conditions, symmetry-resolved information spreading is inhibited due to the competition of coherent and incoherent dynamics: in given quantum number sectors, entropy decreases as a function of time, signalling dynamical purification. Such dynamical purification bridges between two distinct short and intermediate time regimes, characterized by a log-volume and log-area entropy law, respectively. It is generic to symmetric quantum evolution, and as such occurs for different partition geometry and topology, and classes of (local) Liouville dynamics. We then develop a protocol to measure symmetry-resolved entropies and negativities in synthetic quantum systems based on the random unitary toolbox, and demonstrate the generality of dynamical purification using experimental data from trapped ion experiments [Brydges et al., Science 364, 260 (2019)]. Our work shows that symmetry plays a key role as a magnifying glass to characterize many-body dynamics in open quantum systems, and, in particular, in noisy-intermediate scale quantum devices., Comment: 41 pages, 11 figures

Quantum simulation, the simulation of quantum processes on quantum computers, suggests a path forward for the efficient simulation of problems in condensed-matter physics, quantum chemistry, and materials science. While the majority of quantum simulation algorithms are deterministic, a recent surge of ideas has shown that randomization can greatly benefit algorithmic performance. In this work, we introduce a scheme for quantum simulation that unites the advantages of randomized compiling on the one hand and higher-order multi-product formulas, as they are used for example in linear-combination-of-unitaries (LCU) algorithms or quantum error mitigation, on the other hand. In doing so, we propose a framework of randomized sampling that is expected to be useful for programmable quantum simulators and present two new multi-product formula algorithms tailored to it. Our framework reduces the circuit depth by circumventing the need for oblivious amplitude amplification required by the implementation of multi-product formulas using standard LCU methods, rendering it especially useful for early quantum computers used to estimate the dynamics of quantum systems instead of performing full-fledged quantum phase estimation. Our algorithms achieve a simulation error that shrinks exponentially with the circuit depth. To corroborate their functioning, we prove rigorous performance bounds as well as the concentration of the randomized sampling procedure. We demonstrate the functioning of the approach for several physically meaningful examples of Hamiltonians, including fermionic systems and the Sachdev-Ye-Kitaev model, for which the method provides a favorable scaling in the effort., Comment: 24 pages, 6 figures

We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter $x$ and involve execution of a (possibly unknown) quantum process $\mathcal{E}$. Our figure of merit is the number of runs of $\mathcal{E}$ required to achieve a desired prediction performance. We consider classical ML models that perform a measurement and record the classical outcome after each run of $\mathcal{E}$, and quantum ML models that can access $\mathcal{E}$ coherently to acquire quantum data; the classical or quantum data is then used to predict outcomes of future experiments. We prove that for any input distribution $\mathcal{D}(x)$, a classical ML model can provide accurate predictions on average by accessing $\mathcal{E}$ a number of times comparable to the optimal quantum ML model. In contrast, for achieving accurate prediction on all inputs, we prove that exponential quantum advantage is possible. For example, to predict expectations of all Pauli observables in an $n$-qubit system $\rho$, classical ML models require $2^{\Omega(n)}$ copies of $\rho$, but we present a quantum ML model using only $\mathcal{O}(n)$ copies. Our results clarify where quantum advantage is possible and highlight the potential for classical ML models to address challenging quantum problems in physics and chemistry., Comment: 6 pages, 2 figures + 28-page appendix

Quantum computers promise to solve important problems faster than conventional computers. However, unleashing this power has been challenging. In particular, design automation runs into (1) the probabilistic nature of quantum computation and (2) exponential requirements for computational resources on non-quantum hardware. In quantum circuit simulation, Decision Diagrams (DDs) have previously shown to reduce the required memory in many important cases by exploiting redundancies in the quantum state. In this paper, we show that this reduction can be amplified by exploiting the probabilistic nature of quantum computers to achieve even more compact representations. Specifically, we propose two new DD-based simulation strategies that approximate the quantum states to attain more compact representations, while, at the same time, allowing the user to control the resulting degradation in accuracy. We also analytically prove the effect of multiple approximations on the attained accuracy and empirically show that the resulting simulation scheme enables speed-ups up to several orders of magnitudes., Comment: 6 pages, 2 figures, to be published at Design, Automation, and Test in Europe 2021

Recent years have seen unprecedented advance in the design and control of quantum computers. Nonetheless, their applicability is still restricted and access remains expensive. Therefore, a substantial amount of quantum algorithms research still relies on simulating quantum circuits on classical hardware. However, due to the sheer complexity of simulating real quantum computers, many simulators unrealistically simplify the problem and instead simulate perfect quantum hardware, i.e., they do not consider errors caused by the fragile nature of quantum systems. Stochastic quantum simulation provides a conceptually suitable solution to this problem: physically motivated errors are applied in a probabilistic fashion throughout the simulation. In this work, we propose to use decision diagrams, as well as concurrent executions, to substantially reduce resource-requirements-which are still daunting-for stochastic quantum circuit simulation. Backed up by rigorous theory, empirical studies show that this approach allows for a substantially faster and much more scalable simulation for certain quantum circuits., Comment: 6 pages, 1 figure, 1 table

In this work, we consider error detection via simulation for reversible circuit architectures. We rigorously prove that reversibility augments the performance of this simple error detection protocol to a considerable degree. A single randomly generated input is guaranteed to unveil a single error with a probability that only depends on the size of the error, not the size of the circuit itself. Empirical studies confirm that this behavior typically extends to multiple errors as well. In conclusion, reversible circuits offer characteristics that reduce masking effects -- a desirable feature that is in stark contrast to irreversible circuit architectures., Comment: 6 pages, 9 figures

Verification of quantum circuits is essential for guaranteeing correctness of quantum algorithms and/or quantum descriptions across various levels of abstraction. In this work, we show that there are promising ways to check the correctness of quantum circuits using simulative verification and random stimuli. To this end, we investigate how to properly generate stimuli for efficiently checking the correctness of a quantum circuit. More precisely, we introduce, illustrate, and analyze three schemes for quantum stimuli generation---offering a trade-off between the error detection rate (as well as the required number of stimuli) and efficiency. In contrast to the verification in the classical realm, we show (both, theoretically and empirically) that even if only a few randomly-chosen stimuli (generated from the proposed schemes) are considered, high error detection rates can be achieved for quantum circuits. The results of these conceptual and theoretical considerations have also been empirically confirmed---with a grand total of approximately $10^6$ simulations conducted across 50 000 benchmark instances., Comment: 6 pages, in Asia and South Pacific Design Automation Conference (ASP-DAC) 2021

Linear-optical circuits are elementary building blocks for classical and quantum information processing with light. In particular, due to its monolithic structure, integrated photonics offers great phase-stability and can rely on the large scale manufacturability provided by the semiconductor industry. New devices, based on such optical circuits, hold the promise of faster and energy-efficient computations in machine learning applications and even implementing quantum algorithms intractable for classical computers. However, this technological revolution requires accurate and scalable certification protocols for devices that can be comprised of thousands of optical modes. Here, we present a novel technique to reconstruct the transfer matrix of linear optical networks that is based on the recent advances in low-rank matrix recovery and convex optimisation problems known as PhaseLift algorithms. Conveniently, our characterisation protocol can be performed with a coherent classical light source and photodiodes. We prove that this method is robust to noise and scales efficiently with the number of modes. We experimentally tested the proposed characterisation protocol on a programmable integrated interferometer designed for quantum information processing. We compared the transfer matrix reconstruction obtained with our method against the one provided by a more demanding reconstruction scheme based on two-photon quantum interference. For 5-dimensional random unitaries, the average circuit fidelity between the matrices obtained from the two reconstructions is 0.993., Comment: main document: 11 pages with 4 figures, appendix section: 15 pages

Quantum state tomography is a powerful, but resource-intensive, general solution for numerous quantum information processing tasks. This motivates the design of robust tomography procedures that use relevant resources as sparingly as possible. Important cost factors include the number of state copies and measurement settings, as well as classical postprocessing time and memory. In this work, we present and analyze an online tomography algorithm designed to optimize all the aforementioned resources at the cost of a worse dependence on accuracy. The protocol is the first to give provably optimal performance in terms of rank and dimension for state copies, measurement settings and memory. Classical runtime is also reduced substantially and numerical experiments demonstrate a favorable comparison with other state-of-the-art techniques. Further improvements are possible by executing the algorithm on a quantum computer, giving a quantum speedup for quantum state tomography., Comment: Corrected typos and added numerical examples

Quantum simulation has wide applications in quantum chemistry and physics. Recently, scientists have begun exploring the use of randomized methods for accelerating quantum simulation. Among them, a simple and powerful technique, called qDRIFT, is known to generate random product formulas for which the average quantum channel approximates the ideal evolution. qDRIFT achieves a gate count that does not explicitly depend on the number of terms in the Hamiltonian, which contrasts with Suzuki formulas. This work aims to understand the origin of this speed-up by comprehensively analyzing a single realization of the random product formula produced by qDRIFT. The main results prove that a typical realization of the randomized product formula approximates the ideal unitary evolution up to a small diamond-norm error. The gate complexity is already independent of the number of terms in the Hamiltonian, but it depends on the system size and the sum of the interaction strengths in the Hamiltonian. Remarkably, the same random evolution starting from an arbitrary, but fixed, input state yields a much shorter circuit suitable for that input state. In contrast, in deterministic settings, such an improvement usually requires initial state knowledge. The proofs depend on concentration inequalities for vector and matrix martingales, and the framework is applicable to other randomized product formulas. Our bounds are saturated by certain commuting Hamiltonians., Comment: 27 pages, 6 figures

We propose a method for detecting bipartite entanglement in a many-body mixed state based on estimating moments of the partially transposed density matrix. The estimates are obtained by performing local random measurements on the state, followed by post-processing using the classical shadows framework. Our method can be applied to any quantum system with single-qubit control. We provide a detailed analysis of the required number of experimental runs, and demonstrate the protocol using existing experimental data [Brydges et al, Science 364, 260 (2019)]., Comment: 5+10 pages, 7 figures

Predicting properties of complex, large-scale quantum systems is essential for developing quantum technologies. We present an efficient method for constructing an approximate classical description of a quantum state using very few measurements of the state. This description, called a classical shadow, can be used to predict many different properties: order $\log M$ measurements suffice to accurately predict $M$ different functions of the state with high success probability. The number of measurements is independent of the system size, and saturates information-theoretic lower bounds. Moreover, target properties to predict can be selected after the measurements are completed. We support our theoretical findings with extensive numerical experiments. We apply classical shadows to predict quantum fidelities, entanglement entropies, two-point correlation functions, expectation values of local observables, and the energy variance of many-body local Hamiltonians. The numerical results highlight the advantages of classical shadows relative to previously known methods., Comment: 10 pages, 9 figures + 30 page appendix; supersedes arXiv:1908.08909; open source code available at https://github.com/momohuang/predicting-quantum-properties

We investigate an approach for studying the ground state of a quantum many-body Hamiltonian that is based on treating the correlation functions as variational parameters. In this approach, the challenge set by the exponentially-large Hilbert space is circumvented by approximating the positivity of the density matrix, order-by-order, in a way that keeps track of a limited set of correlation functions. In particular, the density-matrix description is replaced by a correlation matrix whose dimension is kept linear in system size, to all orders of the approximation. Unlike the conventional variational principle which provides an upper bound on the ground-state energy, in this approach one obtains a lower bound instead. By treating several one-dimensional spin $1/2$ Hamiltonians, we demonstrate the ability of this approach to produce long-range correlations, and a ground-state energy that converges to the exact result. Possible extensions, including to higher-excited states are discussed., Comment: 8 pages, 6 figures

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., Comment: 64 pages, 4 figures, many diagrams

We give a quantum speedup for solving the canonical semidefinite programming relaxation for binary quadratic optimization. This 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. Such instances include approximating the ground state of spin glasses and MaxCut on Erd\"{o}s-R\'enyi graphs. We also provide an efficient randomized rounding procedure that converts approximately optimal SDP solutions into approximations of the original quadratic optimization problem., Comment: 42 pages, one figure. Corrected several typos and added a more thorough discussion on speedups for random instances. Accepted for publication in Quantum

Predicting features of complex, large-scale quantum systems is essential to the characterization and engineering of quantum architectures. We present an efficient approach for constructing an approximate classical description, called the classical shadow, of a quantum system from very few quantum measurements that can later be used to predict a large collection of features. This approach is guaranteed to accurately predict M linear functions with bounded Hilbert-Schmidt norm from only order of log(M) measurements. This is completely independent of the system size and saturates fundamental lower bounds from information theory. We support our theoretical findings with numerical experiments over a wide range of problem sizes (2 to 162 qubits). These highlight advantages compared to existing machine learning approaches., Comment: 8 pages, 6 figures + 10 page appendix and one reference to Norse mythology

This paper studies the problem of decomposing a low-rank matrix into a factor with binary entries, either from $\{\pm 1\}$ or from $\{0,1\}$, and an unconstrained factor. The research answers fundamental questions about the existence and uniqueness of these decompositions. It also leads to tractable factorization algorithms that succeed under a mild deterministic condition. This work builds on a companion paper that addresses the related problem of decomposing a low-rank positive-semidefinite matrix into symmetric binary factors., Comment: 18(+9) pages, 1 figure

This paper studies the problem of decomposing a low-rank positive-semidefinite matrix into symmetric factors with binary entries, either $\{\pm 1\}$ or $\{0,1\}$. This research answers fundamental questions about the existence and uniqueness of these decompositions. It also leads to tractable factorization algorithms that succeed under a mild deterministic condition. A companion paper addresses the related problem of decomposing a low-rank rectangular matrix into a binary factor and an unconstrained factor., Comment: 21(+4) pages, 3 figures

Compressed sensing is the art of reconstructing structured $n$-dimensional vectors from substantially fewer measurements than naively anticipated. A plethora of analytic reconstruction guarantees support this credo. The strongest among them are based on deep results from large-dimensional probability theory that require a considerable amount of randomness in the measurement design. Here, we demonstrate that derandomization techniques allow for considerably reducing the amount of randomness that is required for such proof strategies. More, precisely we establish uniform s-sparse reconstruction guarantees for $C s \log (n)$ measurements that are chosen independently from strength-four orthogonal arrays and maximal sets of mutually unbiased bases, respectively. These are highly structured families of $\tilde{C} n^2$ vectors that imitate signed Bernoulli and standard Gaussian vectors in a (partially) derandomized fashion., Comment: 12 pages, 2 figures

Projected least squares (PLS) is an intuitive and numerically cheap technique for quantum state tomography. The method first computes the least-squares estimator (or a linear inversion estimator) and then projects the initial estimate onto the space of states. The main result of this paper equips this point estimator with a rigorous, non-asymptotic confidence region expressed in terms of the trace distance. The analysis holds for a variety of measurements, including 2-designs and Pauli measurements. The sample complexity of the estimator is comparable to the strongest convergence guarantees available in the literature and -- in the case of measuring the uniform POVM -- saturates fundamental lower bounds.The results are derived by reinterpreting the least-squares estimator as a sum of random matrices and applying a matrix-valued concentration inequality. The theory is supported by numerical simulations for mutually unbiased bases, Pauli observables, and Pauli basis measurements., Comment: 5+10 pages, 2+1 figures

Gerrymandering is a long-standing issue within the U.S. political system, and it has received scrutiny recently by the U.S. Supreme Court. In this note, we prove that deciding whether there exists a fair redistricting among legal maps is NP-hard. To make this precise, we use simplified notions of "legal" and "fair" that account for desirable traits such as geographic compactness of districts and sufficient representation of voters. The proof of our result is inspired by the work of Mahanjan, Minbhorkar and Varadarajan that proves that planar k-means is NP-hard.

Characterising quantum processes is a key task in and constitutes a challenge for the development of quantum technologies, especially at the noisy intermediate scale of today's devices. One method for characterising processes is randomised benchmarking, which is robust against state preparation and measurement (SPAM) errors, and can be used to benchmark Clifford gates. A complementing approach asks for full tomographic knowledge. Compressed sensing techniques achieve full tomography of quantum channels essentially at optimal resource efficiency. So far, guarantees for compressed sensing protocols rely on unstructured random measurements and can not be applied to the data acquired from randomised benchmarking experiments. It has been an open question whether or not the favourable features of both worlds can be combined. In this work, we give a positive answer to this question. For the important case of characterising multi-qubit unitary gates, we provide a rigorously guaranteed and practical reconstruction method that works with an essentially optimal number of average gate fidelities measured respect to random Clifford unitaries. Moreover, for general unital quantum channels we provide an explicit expansion into a unitary 2-design, allowing for a practical and guaranteed reconstruction also in that case. As a side result, we obtain a new statistical interpretation of the unitarity -- a figure of merit that characterises the coherence of a process. In our proofs we exploit recent representation theoretic insights on the Clifford group, develop a version of Collins' calculus with Weingarten functions for integration over the Clifford group, and combine this with proof techniques from compressed sensing., Comment: 26 pages, 3 figures. V2: Incomplete funding information corrected and minor improvements of the presentation

Quantum process tomography is the task of reconstructing unknown quantum channels from measured data. In this work, we introduce compressed sensing-based methods that facilitate the reconstruction of quantum channels of low Kraus rank. Our main contribution is the analysis of a natural measurement model for this task: We assume that data is obtained by sending pure states into the channel and measuring expectation values on the output. Neither ancillary systems nor coherent operations across multiple channel uses are required. Most previous results on compressed process reconstruction reduce the problem to quantum state tomography on the channel's Choi matrix. While this ansatz yields recovery guarantees from an essentially minimal number of measurements, physical implementations of such schemes would typically involve ancillary systems. A priori, it is unclear whether a measurement model tailored directly to quantum process tomography might require more measurements. We establish that this is not the case. Technically, we prove recovery guarantees for three different reconstruction algorithms. The reconstructions are based on a trace, diamond, and $\ell_2$-norm minimization, respectively. Our recovery guarantees are uniform in the sense that with one random choice of measurement settings all quantum channels can be recovered equally well. Moreover, stability against arbitrary measurement noise and robustness against violations of the low-rank assumption is guaranteed. Numerical studies demonstrate the feasibility of the approach., Comment: 45+11 pages, several figures and plots. v2: Improved version, section on approximate designs added. v3: Small changes and incomplete funding information corrected. v4: Robustness property clarified; published version

The diamond norm plays an important role in quantum information and operator theory. Recently, it has also been proposed as a regularizer for low-rank matrix recovery. The norm constants that bound the diamond norm in terms of the nuclear norm (also known as trace norm) are explicitly known. This note provides a simple characterization of all operators saturating the upper and the lower bound., Comment: Simplified proof of the main theorem in [arXiv:1511.01513] and a converse statement. 3+1 pages. V2: small changes and incomplete funding information corrected. V3: minor polishing, published version

We prove that low-rank matrices can be recovered efficiently from a small number of measurements that are sampled from orbits of a certain matrix group. As a special case, our theory makes statements about the phase retrieval problem. Here, the task is to recover a vector given only the amplitudes of its inner product with a small number of vectors from an orbit. Variants of the group in question have appeared under different names in many areas of mathematics. In coding theory and quantum information, it is the complex Clifford group; in time-frequency analysis the oscillator group; and in mathematical physics the metaplectic group. It affords one particularly small and highly structured orbit that includes and generalizes the discrete Fourier basis: While the Fourier vectors have coefficients of constant modulus and phases that depend linearly on their index, the vectors in said orbit have phases with a quadratic dependence. In quantum information, the orbit is used extensively and is known as the set of stabilizer states. We argue that due to their rich geometric structure and their near-optimal recovery properties, stabilizer states form an ideal model for structured measurements for phase retrieval. Our results hold for $m\geq C \kappa_r r d \log(d)$ measurements, where the oversampling factor k varies between $\kappa_r=1$ and $\kappa_r = r^2$ depending on the orbit. The reconstruction is stable towards both additive noise and deviations from the assumption of low rank. If the matrices of interest are in addition positive semidefinite, reconstruction may be performed by a simple constrained least squares regression. Our proof methods could be adapted to cover orbits of other groups., Comment: 19 pages, no figure

It is a fundamental property of quantum mechanics that information is lost as a result of performing measurements. Indeed, with every quantum measurement one can associate a number -- its POVM norm constant -- that quantifies how much the distinguishability of quantum states degrades in the worst case as a result of the measurement. This raises the obvious question which measurements preserve the most information in these sense of having the largest norm constant. While a number of near-optimal schemes have been found (e.g. the uniform POVM, or complex projective 4-designs), they all seem to be difficult to implement in practice. Here, we analyze the distinguishability of quantum states under measurements that are orbits of the Clifford group. The Clifford group plays an important role e.g. in quantum error correction, and its elements are considered simple to implement. We find that the POVM norm constants of Clifford orbits depend on the effective rank of the states that should be distinguished, as well as on a quantitative measure of the "degree of localization in phase space" of the vectors in the orbit. The most important Clifford orbit is formed by the set of stabilizer states. Our main result implies that stabilizer measurements are essentially optimal for distinguishing pure quantum states. As an auxiliary result, we use the methods developed here to prove new entropic uncertainty relations for stabilizer measurements. This paper is based on a very recent analysis of the representation theory of tensor powers of the Clifford group., Comment: 20 pages, 1 figure

A unitary t-design is a set of unitaries that is "evenly distributed" in the sense that the average of any t-th order polynomial over the design equals the average over the entire unitary group. In various fields -- e.g. quantum information theory -- one frequently encounters constructions that rely on matrices drawn uniformly at random from the unitary group. Often, it suffices to sample these matrices from a unitary t-design, for sufficiently high t. This results in more explicit, derandomized constructions. The most prominent unitary t-design considered in quantum information is the multi-qubit Clifford group. It is known to be a unitary 3-design, but, unfortunately, not a 4-design. Here, we give a simple, explicit characterization of the way in which the Clifford group fails to constitute a 4-design. Our results show that for various applications in quantum information theory and in the theory of convex signal recovery, Clifford orbits perform almost as well as those of true 4-designs. Technically, it turns out that in a precise sense, the 4th tensor power of the Clifford group affords only one more invariant subspace than the 4th tensor power of the unitary group. That additional subspace is a stabilizer code -- a structure extensively studied in the field of quantum error correction codes. The action of the Clifford group on this stabilizer code can be decomposed explicitly into previously known irreps of the discrete symplectic group. We give various constructions of exact complex projective 4-designs or approximate 4-designs of arbitrarily high precision from Clifford orbits. Building on results from coding theory, we give strong evidence suggesting that these orbits actually constitute complex projective 5-designs., Comment: 49 pages, many representations. Not. A. Single. Figure. See also related work by Helsen, Wallman, and Wehner