Search

Estimation of expectation values of incompatible observables is an essential practical task in quantum computing, especially for approximating energies of chemical and other many-body quantum systems. In this work we introduce a method for this purpose based on performing a single joint measurement that can be implemented locally and whose marginals yield noisy (unsharp) versions of the target set of non-commuting Pauli observables. We derive bounds on the number of experimental repetitions required to estimate energies up to a certain precision. We compare this strategy to the classical shadow formalism and show that our method yields the same performance as the locally biased classical shadow protocol. We also highlight some general connections between the two approaches by showing that classical shadows can be used to construct joint measurements and vice versa. Finally, we adapt the joint measurement strategy to minimise the sample complexity when the implementation of measurements is assumed noisy. This can provide significant efficiency improvements compared to known generalisations of classical shadows to noisy scenarios., 14 pages, updated in line with published version

We propose a scheme to implement general quantum measurements, also known as Positive Operator Valued Measures (POVMs) in dimension $d$ using only classical resources and a single ancillary qubit. Our method is based on the probabilistic implementation of $d$-outcome measurements which is followed by postselection of some of the received outcomes. We conjecture that the success probability of our scheme is larger than a constant independent of $d$ for all POVMs in dimension $d$. Crucially, this conjecture implies the possibility of realizing arbitrary nonadaptive quantum measurement protocol on a $d$-dimensional system using a single auxiliary qubit with only a \emph{constant} overhead in sampling complexity. We show that the conjecture holds for typical rank-one Haar-random POVMs in arbitrary dimensions. Furthermore, we carry out extensive numerical computations showing success probability above a constant for a variety of extremal POVMs, including SIC-POVMs in dimension up to 1299. Finally, we argue that our scheme can be favourable for the experimental realization of POVMs, as noise compounding in circuits required by our scheme is typically substantially lower than in the standard scheme that directly uses Naimark's dilation theorem., 5 pages + 14 pages of appendices; v2: improved narration, fixed typos; comments and suggestions are welcome

We introduce a correlated measurement noise model that can be efficiently described and characterized, and which admits effective noise-mitigation on the level of marginal probability distributions. Noise mitigation can be performed up to some error for which we derive upper bounds. Characterization of the model is done efficiently using Diagonal Detector Overlapping Tomography -- a generalization of the recently introduced Quantum Overlapping Tomography to the problem of reconstruction of readout noise with restricted locality. The procedure allows to characterize $k$-local measurement cross-talk on $N$-qubit device using $O(k2^klog(N))$ circuits containing random combinations of X and identity gates. We perform experiments on 15 (23) qubits using IBM's (Rigetti's) devices to test both the noise model and the error-mitigation scheme, and obtain an average reduction of errors by a factor $>22$ ($>5.5$) compared to no mitigation. Interestingly, we find that correlations in the measurement noise do not correspond to the physical layout of the device. Furthermore, we study numerically the effects of readout noise on the performance of the Quantum Approximate Optimization Algorithm (QAOA). We observe in simulations that for numerous objective Hamiltonians, including random MAX-2-SAT instances and the Sherrington-Kirkpatrick model, the noise-mitigation improves the quality of the optimization. Finally, we provide arguments why in the course of QAOA optimization the estimates of the local energy (or cost) terms often behave like uncorrelated variables, which greatly reduces sampling complexity of the energy estimation compared to the pessimistic error analysis. We also show that similar effects are expected for Haar-random quantum states and states generated by shallow-depth random circuits., 27+25 pages, 6+2 figures, 0+3 table, 0+3 algorithmic boxes; v2: fixed typos, added omitted references, expanded acknowledgments; v3: updated to version accepted in Quantum, improved main narration, fixed typos;comments and suggestions are welcome

We present a comprehensive study of the impact of non-uniform, i.e.\ path-dependent, photonic losses on the computational complexity of linear-optical processes. Our main result states that, if each beam splitter in a network induces some loss probability, non-uniform network designs cannot circumvent the efficient classical simulations based on losses. To achieve our result we obtain new intermediate results that can be of independent interest. First, we show that, for any network of lossy beam-splitters, it is possible to extract a layer of non-uniform losses that depends on the network geometry. We prove that, for every input mode of the network it is possible to commute $s_i$ layers of losses to the input, where $s_i$ is the length of the shortest path connecting the $i$th input to any output. We then extend a recent classical simulation algorithm due to P. Clifford and R. Clifford to allow for arbitrary $n$-photon input Fock states (i.e. to include collision states). Consequently, we identify two types of input states where boson sampling becomes classically simulable: (A) when $n$ input photons occupy a constant number of input modes; (B) when all but $O(\log n)$ photons are concentrated on a single input mode, while an additional $O(\log n)$ modes contain one photon each., Comment: 14 pages, 5 figures, v4: final version accepted in Quantum, acknowledgements slightly modified

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 establish 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\simeq\frac{d^{5/2}}{\epsilon}$ and $\delta=\left(\frac{\epsilon^{3/2}}{d}\right)^{d^2}$. We also show that $\epsilon$-nets can be used to construct $\delta$-approximate unitary $t$-designs for $\delta= \epsilon t$. Finally, we prove that the degree of an exact unitary $t$-design necessary to obtain an $\epsilon$-net must grow at least fast as $\frac1\epsilon$ (for fixed $d$) and not slower than $d^2$ (for fixed $\epsilon$). This shows near optimality of our result connecting $t$-designs and $\epsilon$-nets. We apply our findings 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. Our gate sets need not to be symmetric (i.e. contain gates together with their inverses) or consist of gates with algebraic entries. We also show 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., Comment: 26 pages + 17 pages of appendix, 3 figures, accepted in IEEE: Transactions in Information Theory, Important changes in ver 3: (i) Corrected estimates for volumes of balls in projective unitary group, (ii) bounds on the L1 of the approximation to the Dirac delta given. (iii) updated references

Fermionic Linear Optics (FLO) is a restricted model of quantum computation which in its original form is known to be efficiently classically simulable. We show that, when initialized with suitable input states, FLO circuits can be used to demonstrate quantum computational advantage with strong hardness guarantees. Based on this, we propose a quantum advantage scheme which is a fermionic analogue of Boson Sampling: Fermion Sampling with magic input states. We consider in parallel two classes of circuits: particle-number conserving (passive) FLO and active FLO that preserves only fermionic parity and is closely related to Matchgate circuits introduced by Valiant. Mathematically, these classes of circuits can be understood as fermionic representations of the Lie groups $U(d)$ and $SO(2d)$. This observation allows us to prove our main technical results. We first show anticoncentration for probabilities in random FLO circuits of both kind. Moreover, we prove robust average-case hardness of computation of probabilities. To achieve this, we adapt the worst-to-average-case reduction based on Cayley transform, introduced recently by Movassagh, to representations of low-dimensional Lie groups. Taken together, these findings provide hardness guarantees comparable to the paradigm of Random Circuit Sampling. Importantly, our scheme has also a potential for experimental realization. Both passive and active FLO circuits are relevant for quantum chemistry and many-body physics and have been already implemented in proof-of-principle experiments with superconducting qubit architectures. Preparation of the desired quantum input states can be obtained by a simple quantum circuit acting independently on disjoint blocks of four qubits and using 3 entangling gates per block. We also argue that due to the structured nature of FLO circuits, they can be efficiently certified., Comment: 65 pages, 13 figures, 1 table, v2: improved discussion and narrative, numerics about anticoncentration added, references updated, comments and suggestions are welcome

We present new results concerning simulation of general quantum measurements (POVMs) by projective measurements (PMs) for the task of Unambiguous State Discrimination (USD). We formulate a problem of finding optimal strategy of simulation for given quantum measurement. The problem can be solved for qubit and qutrits measurements by Semi-Definite Programming (SDP) methods.

We report an alternative scheme for implementing generalized quantum measurements that does not require the usage of auxiliary system. Our method utilizes solely: (a) classical randomness and post-processing, (b) projective measurements on a relevant quantum system and (c) postselection on non-observing certain outcomes. The scheme implements arbitrary quantum measurement in dimension $d$ with the optimal success probability $1/d$. We apply our results to bound the relative power of projective and generalised measurements for unambiguous state discrimination. Finally, we test our scheme experimentally on IBM's quantum processor. Interestingly, due to noise involved in the implementation of entangling gates, the quality with which our scheme implements generalized qubit measurements outperforms the standard construction using the auxiliary system., 7 + 3 pages, 1 + 2 figures, 1 + 0 tables, comments and suggestions are welcome; v2: improved narrative in the main text, proofs of some technical details were moved to the appendix; v3: changed title, improved narrative in the main text, corrected typos in Appendix (matrix elements of tetrahedral measurement)

We propose a simple scheme to reduce readout errors in experiments on quantum systems with finite number of measurement outcomes. Our method relies on performing classical post-processing which is preceded by Quantum Detector Tomography, i.e., the reconstruction of a Positive-Operator Valued Measure (POVM) describing the given quantum measurement device. If the measurement device is affected only by an invertible classical noise, it is possible to correct the outcome statistics of future experiments performed on the same device. To support the practical applicability of this scheme for near-term quantum devices, we characterize measurements implemented in IBM's and Rigetti's quantum processors. We find that for these devices, based on superconducting transmon qubits, classical noise is indeed the dominant source of readout errors. Moreover, we analyze the influence of the presence of coherent errors and finite statistics on the performance of our error-mitigation procedure. Applying our scheme on the IBM's 5-qubit device, we observe a significant improvement of the results of a number of single- and two-qubit tasks including Quantum State Tomography (QST), Quantum Process Tomography (QPT), the implementation of non-projective measurements, and certain quantum algorithms (Grover's search and the Bernstein-Vazirani algorithm). Finally, we present results showing improvement for the implementation of certain probability distributions in the case of five qubits., 18 + 5 pages, 11+2 figures, 5+1 tables, comments and suggestions are welcome; v2: version accepted in Quantum, updated references, fixed figures formatting, improved style and narrative in the main text, added note about code availability

We present an in-depth study of the problem of multiple-shot discrimination of von Neumann measurements in finite-dimensional Hilbert spaces. Specifically, we consider two scenarios: minimum error and unambiguous discrimination. In the case of minimum error discrimination, we focus on discrimination of measurements with the assistance of entanglement. We provide an alternative proof of the fact that all pairs of distinct von Neumann measurements can be distinguished perfectly (i.e. with the unit success probability) using only a finite number of queries. Moreover, we analytically find the minimal number of queries needed for perfect discrimination. We also show that in this scenario querying the measurements gives the optimal strategy, and hence any possible adaptive methods do not offer any advantage over the parallel scheme. In the unambiguous discrimination scenario, we give the general expressions for the optimal discrimination probabilities with and without the assistance of entanglement. Finally, we show that typical pairs of Haar-random von Neumann measurements can be perfectly distinguished with only two queries., Comment: 19 pages, 9 figures

The so-called preparation uncertainty can be understood in purely operational terms. Namely, it occurs when for some pair of observables, there is no preparation, for which they both exhibit deterministic statistics. However, the right-hand side of uncertainty relation is generally not operational as it depends on the quantum formalism. Also, while joint non-measurability of observables is an operational notion, the complementarity in Bohr sense (i.e. excess of information needed to describe the system) has not yet been expressed in purely operational terms. In this paper we propose a solution to these problems, by introducing an operational definition for complementarity, and further postulating uncertainty as a necessary price for complementarity in physical theories. In other words, we propose to put the (operational) complementarity as the right-hand side of uncertainty relation. Concretely, we first identify two different notions of uncertainty and complementarity for which the above principle holds in quantum mechanics. We also introduce postulates for the general measures of uncertainty and complementarity. In order to define quantifiers of complementarity we first turn to the simpler notion of independence that is defined solely in terms of statistics two observables. We also use our framework to define new complementarity indicators based on (i) performance of random access codes, (ii) geometrical properties of the body of observed statistics, and (iii) variation of information. We then show that they can be used to state uncertainty relations. Moreover, we show that non-signaling and uncertainty relation expressed by complementarity of type (ii) leads to the Tsirelson bound for CHSH inequality. Lastly, we show that a variant of Information Causality called Information Content Principle, can be interpreted as uncertainty relation in the above sense., 24 pages, 13 Figures, Comments and suggestions are welcome, v3: additional results about RACs added, more emphasis put on the interplay between convexity of physical theories and complementarity

In any theory satisfying the no-signaling principle correlations generated among spatially separated parties in a Bell-type experiment are subject to certain constraints known as monogamy relations. Recently, in the context of the black hole information loss problem it was suggested that these monogamy relations might be violated. This in turn implies that correlations arising in such a scenario must violate the no-signaling principle and hence can be used to send classical information between parties. Here, we study the amount of information that can be sent using such correlations. To this aim, we first provide a framework associating them with classical channels whose capacities are then used to quantify the usefulness of these correlations in sending information. Finally, we determine the minimal amount of information that can be sent using signaling correlations violating the monogamy relation associated to the chained Bell inequalities., Comment: 14 pages, 2 figures; improved version; accepted for publication in Foundations of Physics

We explore the possibility of efficient classical simulation of linear optics experiments under the effect of particle losses. Specifically, we investigate the canonical boson sampling scenario in which an $n$-particle Fock input state propagates through a linear-optical network and is subsequently measured by particle-number detectors in the $m$ output modes. We examine two models of losses. In the first model a fixed number of particles is lost. We prove that in this scenario the output statistics can be well approximated by an efficient classical simulation, provided that the number of photons that is left grows slower than $\sqrt{n}$. In the second loss model, every time a photon passes through a beamsplitter in the network, it has some probability of being lost. For this model the relevant parameter is $s$, the smallest number of beamsplitters that any photon traverses as it propagates through the network. We prove that it is possible to approximately simulate the output statistics already if $s$ grows logarithmically with $m$, regardless of the geometry of the network. The latter result is obtained by proving that it is always possible to commute $s$ layers of uniform losses to the input of the network regardless of its geometry, which could be a result of independent interest. We believe that our findings put strong limitations on future experimental realizations of quantum computational supremacy proposals based on boson sampling., 26 pages, 14 figures, comments and suggestions are welcome

For numerous applications of quantum theory it is desirable to be able to apply arbitrary unitary operations on a given quantum system. However, in particular situations only a subset of unitary operations is easily accessible. This raises the question of what additional unitary gates should be added to a given gate-set in order to attain physical universality, i.e., to be able to perform arbitrary unitary transformation on the relevant Hilbert space. In this work, we study this problem for three paradigmatic cases of naturally occurring restricted gate-sets: (A) particle-number preserving bosonic linear optics, (B) particle-number preserving fermionic linear optics, and (C) general (not necessarily particle-number preserving) fermionic linear optics. Using tools from group theory and control theory, we classify, in each of these scenarios, what sets of gates are generated, if an additional gate is added to the set of allowed transformations. This allows us to solve the universality problem completely for arbitrary number of particles and for arbitrary dimensions of the single-particle Hilbert space., 4 pages, 2 figures, 16 pages of appendix, comments and suggestions are welcome

The battle to improve measurement precision constantly forces scientists to develop more and more sophisticated methods. Surprisingly, theoretical demonstration shows that identical bosons, even when prepared in a random and noisy quantum state, can be used to attain precision surpassing that of classical statistics.

We develop a general theory to estimate magnetic field gradients in quantum metrology. We consider a system of $N$ particles distributed on a line whose internal degrees of freedom interact with a magnetic field. Usually gradient estimation is based on precise measurements of the magnetic field at two different locations, performed with two independent groups of particles. This approach, however, is sensitive to fluctuations of the off-set field determining the level-splitting of the particles and results in collective dephasing. In this work we use the framework of quantum metrology to assess the maximal accuracy for gradient estimation. For arbitrary positioning of particles, we identify optimal entangled and separable states allowing the estimation of gradients with the maximal accuracy, quantified by the quantum Fisher information. We also analyze the performance of states from the decoherence-free subspace (DFS), which are insensitive to the fluctuations of the magnetic offset field. We find that these states allow to measure a gradient directly, without the necessity of estimating the magnetic offset field. Moreover, we show that DFS states attain a precision for gradient estimation comparable to the optimal entangled states. Finally, for the above classes of states we find simple and feasible measurements saturating the quantum Cram\'er-Rao bound., Comment: 22 pages, 8 figures. See also the related work by I. Apellaniz et al. arXiv: 1703.09056 (2017)

We review a geometric approach to classification and examination of quantum correlations in composite systems. Since quantum information tasks are usually achieved by manipulating spin and alike systems or, in general, systems with a finite number of energy levels, classification problems are usually treated in frames of linear algebra. We proposed to shift the attention to a geometric description. Treating consistently quantum states as points of a projective space rather than as vectors in a Hilbert space we were able to apply powerful methods of differential, symplectic and algebraic geometry to attack the problem of equivalence of states with respect to the strength of correlations, or, in other words, to classify them from this point of view. Such classifications are interpreted as identification of states with `the same correlations properties' i.e. ones that can be used for the same information purposes, or, from yet another point of view, states that can be mutually transformed one to another by specific, experimentally accessible operations. It is clear that the latter characterization answers the fundamental question `what can be transformed into what \textit{via} available means?'. Exactly such an interpretations, i.e, in terms of mutual transformability can be clearly formulated in terms of actions of specific groups on the space of states and is the starting point for the proposed methods., Comment: 29 pages, 9 figures, 2 tables, final form submitted to the journal

Standard projective measurements represent a subset of all possible measurements in quantum physics, defined by positive-operator-valued measures. We study what quantum measurements are projective simulable, that is, can be simulated by using projective measurements and classical randomness. We first prove that every measurement on a given quantum system can be realised by classical processing of projective measurements on the system plus an ancilla of the same dimension. Then, given a general measurement in dimension two or three, we show that deciding whether it is projective-simulable can be solved by means of semi-definite programming. We also establish conditions for the simulation of measurements using projective ones valid for any dimension. As an application of our formalism, we improve the range of visibilities for which two-qubit Werner states do not violate any Bell inequality for all measurements. From an implementation point of view, our work provides bounds on the amount of noise a measurement tolerates before losing any advantage over projective ones., v2: 4 pages + 12.5 pages of appendices, 2 figures, updated references and narrative, computational appendix is available at https://github.com/peterwittek/ipython-notebooks/blob/master/Simulating_POVMs.ipynb, comments and suggestions are welcome

The superposition principle is one of the landmarks of quantum mechanics. The importance of quantum superpositions provokes questions about the limitations that quantum mechanics itself imposes on the possibility of their generation. In this work we systematically study the problem of creation of superpositions of unknown quantum states. First, we prove a no-go theorem that forbids the existence of a universal probabilistic quantum protocol producing a superposition of two unknown quantum states. Secondly, we provide an explicit probabilistic protocol generating a superposition of two unknown states, each having a fixed overlap with the known referential pure state. The protocol is proven to be unique and optimal. Moreover, it can be implemented on arbitrary Hilbert spaces. In the context of quantum optics it can be used to efficiently generate highly nonclassical or nongaussian states., 4.5 pages + 4.5 pages of Appandix, 4 figures, updated discussion on the Alvarez-Rodriguez et. al. article arxiv:1411.4534, updated references, accepted for publication in PRL

Fermionic linear optics is a model of quantum computation which is efficiently simulable on a classical probabilistic computer. We study the problem of a classical simulation of fermionic linear optics augmented with noisy auxiliary states. If the auxiliary state can be expressed as a convex combination of pure Fermionic Gaussian states, the corresponding computation scheme is classically simulable. We present an analytic characterisation of the set of convex-Gaussian states in the first non-trivial case, in which the Hilbert space of the ancilla is a four-mode Fock space. We use our result to solve an open problem recently posed by De Melo et al. and to study in detail the geometrical properties of the set of convex-Gaussian states., 4 Pages

For several types of correlations: mixed-state entanglement in systems of distinguishable particles, particle entanglement in systems of indistinguishable bosons and fermions and non-Gaussian correlations in fermionic systems we estimate the fraction of non-correlated states among the density matrices with the same spectra. We prove that for the purity exceeding some critical value (depending on the considered problem) fraction of non-correlated states tends to zero exponentially fast with the dimension of the relevant Hilbert space. As a consequence a state randomly chosen from the set of density matrices possessing the same spectra is asymptotically a correlated one. To prove this we developed a systematic framework for detection of correlations via nonlinear witnesses., Comment: 7 pages, 1 figure, title changed, abstract and introduction rewritten, one reference added

We construct nonlinear multiparty entanglement measures for distinguishable particles, bosons and fermions. In each case properties of an entanglement measures are related to the decomposition of the suitably chosen representation of the relevant symmetry group onto irreducible components. In the case of distinguishable particles considered entanglement measure reduces to the well-known many particle concurrence. We prove that our entanglement criterion is sufficient and necessary for pure states living in both finite and infinite dimensional spaces. We generalize our entanglement measures to mixed states by the convex roof extension and give a non trivial lower bound of thus obtained generalized concurrence., minor changes added to the manuscript

We show that multipartite mixed bipartite CC and CQ states are geometrically and topologically distinguished in the space of states. They are characterized by non-vanishing Euler-Poincar\'{e} characteristics on the topological side and by the existence of symplectic structure on the geometric side., Comment: Corrected version, Accepted for publication in JMP

We present a general algorithm for finding all classes of pure multiparticle states equivalent under stochastic local operations and classical communication (SLOCC). We parametrize all SLOCC classes by the critical sets of the total variance function. Our method works for arbitrary systems of distinguishable and indistinguishable particles. We also show how to calculate the Morse indices of critical points which have the interpretation of the number of independent nonlocal perturbations increasing the variance and hence entanglement of a state. We illustrate our method by two examples.

We give a criterion of classicality for mixed states in terms of expectation values of a quantum observable. Using group representation theory we identify all cases when the criterion can be computed exactly in terms of the spectrum of a single operator., 15 pages, Some typos fixed, Theorem 2 supplemented by two originally missing cases, two references added

We analyze form the topological perspective the space of all SLOCC (Stochastic Local Operations with Classical Communication) classes of pure states for composite quantum systems. We do it for both distinguishable and indistinguishable particles. In general, the topology of this space is rather complicated as it is a non-Hausdorff space. Using geometric invariant theory (GIT) and momentum map geometry we propose a way to divide the space of all SLOCC classes into mathematically and physically meaningful families. Each family consists of possibly many `asymptotically' equivalent SLOCC classes. Moreover, each contains exactly one distinguished SLOCC class on which the total variance (a well defined measure of entanglement) of the state Var[v] attains maximum. We provide an algorithm for finding critical sets of Var[v], which makes use of the convexity of the momentum map and allows classification of such defined families of SLOCC classes. The number of families is in general infinite. We introduce an additional refinement into finitely many groups of families using the recent developments in the momentum map geometry known as Ness stratification. We also discuss how to define it equivalently using the convexity of the momentum map applied to SLOCC classes. Moreover, we note that the Morse index at the critical set of the total variance of state has an interpretation of number of non-SLOCC directions in which entanglement increases and calculate it for several exemplary systems. Finally, we introduce the SLOCC-invariant measure of entanglement as a square root of the total variance of state at the critical point and explain its geometric meaning., 37 pages, 2 figures, changes in the manuscript structure

Given L-qubit states with the fixed spectra of reduced one-qubit density matrices, we find a formula for the minimal number of invariant polynomials needed for solving local unitary (LU) equivalence problem, that is, problem of deciding if two states can be connected by local unitary operations. Interestingly, this number is not the same for every collection of the spectra. Some spectra require less polynomials to solve LU equivalence problem than others. The result is obtained using geometric methods, i.e. by calculating the dimensions of reduced spaces, stemming from the symplectic reduction procedure., 22 pages