Search

Quantum complexity is a measure of the minimal number of elementary operations required to approximately prepare a given state or unitary channel. Recently, this concept has found applications beyond quantum computing—in studying the dynamics of quantum many-body systems and the long-time properties of anti–de Sitter black holes. In this context, Brown and Susskind [Phys. Rev. D 97, 086015 (2018)PRVDAQ2470-001010.1103/PhysRevD.97.086015] conjectured that the complexity of a chaotic quantum system grows linearly in time up to times exponential in the system size, saturating at a maximal value, and remaining maximally complex until undergoing recurrences at doubly exponential times. In this work, we prove the saturation and recurrence of complexity in two models of chaotic time evolutions based on (i) random local quantum circuits and (ii) stochastic local Hamiltonian evolution. Our results advance an understanding of the long-time behavior of chaotic quantum systems and could shed light on the physics of black-hole interiors. From a technical perspective, our results are based on establishing new quantitative connections between the Haar measure and high-degree approximate designs, as well as the fact that random quantum circuits of sufficiently high depth converge to approximate designs.

We present a classical algorithm for simulating universal quantum circuits composed of "free" nearest-neighbour matchgates or equivalently fermionic-linear-optical (FLO) gates, and "resourceful" non-Gaussian gates. We achieve the promotion of the efficiently simulable FLO subtheory to universal quantum computation by gadgetizing controlled phase gates with arbitrary phases employing non-Gaussian resource states. Our key contribution is the development of a novel phase-sensitive algorithm for simulating FLO circuits. This allows us to decompose the resource states arising from gadgetization into free states at the level of statevectors rather than density matrices. The runtime cost of our algorithm for estimating the Born-rule probability of a given quantum circuit scales polynomially in all circuit parameters, except for a linear dependence on the newly introduced FLO $extent$, which scales exponentially with the number of controlled-phase gates. More precisely, as a result of finding optimal decompositions of relevant resource states, the runtime doubles for every maximally resourceful (e.g., swap or CZ) gate added. Crucially, this cost compares very favourably with the best known prior algorithm, where each swap gate increases the simulation cost by a factor of approximately 9. For a quantum circuit containing arbitrary FLO unitaries and $k$ controlled-Z gates, we obtain an exponential improvement $O(4.5^k)$ over the prior state-of-the-art.

Abstract 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 probabilistic implementation of d-outcome measurements which is followed by postselection of some of the received outcomes. We conjecture that 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 d-dimensional system using a single auxiliary qubit with only a 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 favorable for 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.

The geometrical arrangement of a set of quantum states can be completely characterized using relational information only. This information is encoded in the pairwise state overlaps, as well as in Bargmann invariants of higher degree written as traces of products of density matrices. We describe how to measure Bargmann invariants using suitable generalizations of the SWAP test. This allows for a complete and robust characterization of the projective-unitary invariant properties of any set of pure or mixed states. As applications, we describe basis-independent tests for linear independence, coherence, and imaginarity. We also show that Bargmann invariants can be used to characterize multi-photon indistinguishability.

Boson sampling (BS) is viewed to be an accessible quantum computing paradigm to demonstrate computational advantage compared to classical computers. In this context, the evolution of permanent calculation algorithms attracts a significant attention as the simulation of BS experiments involves the evaluation of vast number of permanents. For this reason, we generalize the Balasubramanian–Bax–Franklin–Glynn permanent formula, aiming to efficiently integrate it into the BS strategy of Clifford and Clifford (2020 Faster classical boson sampling). A reduction in simulation complexity originating from multiplicities in photon occupation was achieved through the incorporation of a n-ary Gray code ordering of the addends during the permanent evaluation. Implementing the devised algorithm on FPGA-based data-flow engines, we leverage the resulting tool to accelerate boson sampling simulations for up to 40 photons. Drawing samples from a 60-mode interferometer, the achieved rate averages around 80 s per sample, employing 4 FPGA chips. The developed design facilitates the simulation of both ideal and lossy boson sampling experiments.

We introduce distance measures between quantum states, measurements, and channels based on their statistical distinguishability in generic experiments. Specifically, we analyze the average Total Variation Distance (TVD) between output statistics of protocols in which quantum objects are intertwined with random circuits and measured in standard basis. We show that for circuits forming approximate 4-designs, the average TVDs can be approximated by simple explicit functions of the underlying objects – the average-case distances (ACDs). We apply them to analyze the effects of noise in quantum advantage experiments and for efficient discrimination of high-dimensional states and channels without quantum memory. We argue that ACDs are better suited for assessing the quality of NISQ devices than common distance measures such as trace distance or the diamond norm.

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 analog 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. Using low-dimensional continuous symmetry groups that underpin these classes of quantum circuits, we prove anticoncentration and robust average-case hardness of computation of output probabilities probabilities. Taken together, these findings provide hardness guarantees comparable to the paradigm of random circuit sampling and boson sampling, the leading candidates for attaining quantum computational advantage. Our scheme is experimentally feasible. FLO circuits are relevant for quantum chemistry and many-body physics, and have been successfully implemented in superconducting architectures. We also argue that due to the structured nature of FLO circuits, they can be efficiently certified using resources scaling polynomially with the system size, with partial trust in the quantum device.

Measurement noise is one of the main sources of errors in currently available quantum devices based on superconducting qubits. At the same time, the complexity of its characterization and mitigation often exhibits exponential scaling with the system size. In this work, 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.

We consider the problem of certification of arbitrary ensembles of pure states and projective measurements solely from the experimental statistics in the prepare-and-measure scenario assuming the upper bound on the dimension of the Hilbert space. To this aim, we propose a universal and intuitive scheme based on establishing perfect correlations between target states and suitably-chosen projective measurements. The method works in all finite dimensions and allows for robust certification of the overlaps between arbitrary preparation states and between the corresponding measurement operators. Finally, we prove that for qubits, our technique can be used to robustly self-test arbitrary configurations of pure quantum states and projective measurements. These results pave the way towards the practical application of the prepare-and-measure paradigm to certification of quantum devices.

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 $\textit{in parallel}$ 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.

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.

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.

For any resource theory it is essential to identify tasks for which resource objects offer advantage over free objects. We show that this identification can always be accomplished for resource theories of quantum measurements in which free objects form a convex subset of measurements on a given Hilbert space. To this aim we prove that every resourceful measurement offers advantage for some quantum state discrimination task. Moreover, we give an operational interpretation of robustness, which quantifies the minimal amount of noise that must be added to a measurement to make it free. Specifically, we show that this geometric quantity is related to the maximal relative advantage that a resourceful measurement offers in a class of minimal-error state discrimination (MESD) problems. Finally, we apply our results to two classes of free measurements: incoherent measurements (measurements that are diagonal in the fixed basis) and separable measurements (measurements whose effects are separable operators). For both of these scenarios we find, in the asymptotic setting in which the dimension or the number of particles increase to infinity, the maximal relative advantage that resourceful measurements offer for state discrimination tasks.

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.