Search

Estimating quantum partition functions is a critical task in a variety of fields. However, the problem is classically intractable in general due to the exponential scaling of the Hamiltonian dimension $N$ in the number of particles. This paper introduces a quantum algorithm for estimating the partition function $Z_\beta$ of a generic Hamiltonian $H$ up to multiplicative error based on a quantum coin toss. The coin is defined by the probability of applying the quantum imaginary-time evolution propagator $f_\beta[H]=e^{-\beta H/{2}}$ at inverse temperature $\beta$ to the maximally mixed state, realized by a block-encoding of $f_\beta[H]$ into a unitary quantum circuit followed by a post-selection measurement. Our algorithm does not use costly subroutines such as quantum phase estimation or amplitude amplification; and the binary nature of the coin allows us to invoke tools from Bernoulli-process analysis to prove a runtime scaling as $\mathcal{O}(N/{Z_\beta})$, quadratically better than previous general-purpose algorithms using similar quantum resources. Moreover, since the coin is defined by a single observable, the method lends itself well to quantum error mitigation. We test this in practice with a proof-of-concept 9-qubit experiment, where we successfully mitigate errors through a simple noise-extrapolation procedure. Our findings offer an interesting alternative for quantum partition function estimation relevant to early-fault quantum hardware., Comment: 10 pages + 1 appendix, 3 figures

We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexity of two primitive problems: given a function $f$ and a Hermitian matrix $A$, compute a matrix element of $f(A)$ or compute a local measurement on $f(A)|0\rangle^{\otimes n}$, with $|0\rangle^{\otimes n}$ an $n$-qubit reference state vector, in both cases up to additive approximation error. We consider four functions -- monomials, Chebyshev polynomials, the time evolution function, and the inverse function -- and probe the complexity across a broad landscape covering different problem input regimes. Namely, we consider two types of matrix inputs (sparse and Pauli access), matrix properties (norm, sparsity), the approximation error, and function-specific parameters. We identify BQP-complete forms of both problems for each function and then toggle the problem parameters to easier regimes to see where hardness remains, or where the problem becomes classically easy. As part of our results we make concrete a hierarchy of hardness across the functions; in parameter regimes where we have classically efficient algorithms for monomials, all three other functions remain robustly BQP-hard, or hard under usual computational complexity assumptions. In identifying classically easy regimes, among others, we show that for any polynomial of degree $\mathrm{poly}(n)$ both problems can be efficiently classically simulated when $A$ has $O(\log n)$ non-zero coefficients in the Pauli basis. This contrasts with the fact that the problems are BQP-complete in the sparse access model even for constant row sparsity, whereas the stated Pauli access efficiently constructs sparse access with row sparsity $O(\log n)$. Our work provides a catalog of efficient quantum and classical algorithms for fundamental linear-algebra tasks., Comment: 11+28 pages, 1 table, 2 figures

Quantum annealing and quantum approximate optimization algorithms hold a great potential to speed-up optimization problems. This could be game-changing for a plethora of applications. Yet, in order to hope to beat classical solvers, quantum circuits must scale up to sizes and performances much beyond current hardware. In that quest, intense experimental effort has been recently devoted to optimizations on 3-regular graphs, which are computationally hard but experimentally relatively amenable. However, even there, the amount and quality of quantum resources required for quantum solvers to outperform classical ones is unclear. Here, we show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000 two-qubit gates with all-to-all connectivity. To this end, we develop a graph tensor-network quantum annealer (GTQA) able of high-precision simulations of Trotterized circuits of near-adiabatic evolutions. Based on a recently proposed belief-propagation technique for tensor canonicalization, GTQA is equipped with re-gauging and truncation primitives that keep approximation errors small in spite of the circuits generating significant amounts of entanglement. As a result, even with a maximal bond dimension as low as 4, GTQA produces solutions competitive with those of state-of-the-art classical solvers. For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states. In contrast, for degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states. On one hand, our findings showcase the potential of GTQA as a powerful quantum-inspired optimizer. On the other hand, they considerably raise the bar required for experimental demonstrations of quantum speed-ups in combinatorial optimizations.

Nonstabilizerness or `magic' is a key resource for quantum computing and a necessary condition for quantum advantage. Non-Clifford operations turn stabilizer states into resourceful states, where the amount of nonstabilizerness is quantified by resource measures such as stabilizer R\'enyi entropies (SREs). Here, we show that SREs saturate their maximum value at a critical number of non-Clifford operations. Close to the critical point SREs show universal behavior. Remarkably, the derivative of the SRE crosses at the same point independent of the number of qubits and can be rescaled onto a single curve. We find that the critical point depends non-trivially on R\'enyi index $\alpha$. For random Clifford circuits doped with T-gates, the critical T-gate density scales independently of $\alpha$. In contrast, for random Hamiltonian evolution, the critical time scales linearly with qubit number for $\alpha>1$, while is a constant for $\alpha<1$. This highlights that $\alpha$-SREs reveal fundamentally different aspects of nonstabilizerness depending on $\alpha$: $\alpha$-SREs with $\alpha<1$ relate to Clifford simulation complexity, while $\alpha>1$ probe the distance to the closest stabilizer state and approximate state certification cost via Pauli measurements. As technical contributions, we observe that the Pauli spectrum of random evolution can be approximated by two highly concentrated peaks which allows us to compute its SRE. Further, we introduce a class of random evolution that can be expressed as random Clifford circuits and rotations, where we provide its exact SRE. Our results opens up new approaches to characterize the complexity of quantum systems., Comment: 14 pages, 9 figures

We present an exact $n$-qubit computational-basis amplitude encoder of real- or complex-valued data vectors of $d=\binom{n}{k}$ components into a subspace of fixed Hamming weight $k$. This represents a polynomial space compression. The circuit is optimal in that it expresses an arbitrary data vector using only $d-1$ (controlled) Reconfigurable Beam Splitter (RBS) gates and is constructed by an efficient classical algorithm that sequentially generates all bitstrings of weight $k$ and identifies all gate parameters. An explicit compilation into CNOTs and single-qubit gates is presented, with the total CNOT-gate count of $\mathcal{O}(k\, d)$ provided in analytical form. In addition, we show how to load data in the binary basis by sequentially stacking encoders of different Hamming weights using $\mathcal{O}(d\,\log(d))$ CNOT gates. Moreover, using generalized RBS gates that mix states of different Hamming weights, we extend the construction to efficiently encode arbitrary sparse vectors. Finally, we perform an experimental proof-of-principle demonstration of our scheme on a commercial trapped-ion quantum computer. We successfully upload a $q$-Gaussian probability distribution in the non-log-concave regime with $n = 6$ and $k = 2$. We also showcase how the effect of hardware noise can be alleviated by quantum error mitigation. Our results constitute a versatile framework for quantum data compression with various potential applications in fields such as quantum chemistry, quantum machine learning, and constrained combinatorial optimizations., Comment: 13 pages, 7 figures, 4 tables; Revised text + new experimental data

We present a robust shadow estimation protocol for wide classes of shallow measurement circuits that mitigates noise as long as the effective measurement map is locally unitarily invariant. This is in practice an excellent approximation, encompassing for instance the case of ideal single-qubit Clifford gates composing the first circuit layer of an otherwise arbitrary circuit architecture and even non-Markovian, gate-dependent noise in the rest of the circuit. We argue that for approximately local noise the measurement channel has an efficient matrix-product (tensor-train) representation, and show how to estimate this directly from experimental data using tensor-network tools, eliminating the need for analytical or numeric calculations. We illustrate the relevance of our method with both numerics and proof-of-principle experiments on an IBM Q device. Numerically, we show that, while unmitigated shallow shadows with noisy circuits become more biased as the depth increases, robust ones become more accurate for relevant parameter regimes. Experimentally, we observe major bias reductions in two simple fidelity estimation tasks using 5-qubit circuits with up to 2 layers of entangling gates using the mitigated variant, of close to an order of magnitude for $10^4$ measurement shots, e.g. Under the practical constraints of current and near-term noisy quantum devices, our method maximally realizes the potential of shadow estimation with global rotations., Comment: 11 pages, 9 figures

We introduce a variational quantum solver for combinatorial optimizations over $m=\mathcal{O}(n^k)$ binary variables using only $n$ qubits, with tunable $k>1$. The number of parameters and circuit depth display mild linear and sublinear scalings in $m$, respectively. Moreover, we analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature. This leads to unprecedented quantum-solver performances. For $m=7000$, numerical simulations produce solutions competitive in quality with state-of-the-art classical solvers. In turn, for $m=2000$, an experiment with $n=17$ trapped-ion qubits featured MaxCut approximation ratios estimated to be beyond the hardness threshold $0.941$. To our knowledge, this is the highest quality attained experimentally on such sizes. Our findings offer a novel heuristics for quantum-inspired solvers as well as a promising route towards solving commercially-relevant problems on near term quantum devices.

Computational fluid dynamics is both a thriving research field and a key tool for advanced industry applications. The central challenge is to simulate turbulent flows in complex geometries, a compute-power intensive task due to the large vector dimensions required by discretized meshes. We present a full-stack method to solve for incompressible fluids with memory and runtime scaling poly-logarithmically in the mesh size. Our framework is based on matrix-product states, a powerful compressed representation of quantum states. It is complete in that it solves for flows around immersed objects of arbitrary geometries, with non-trivial boundary conditions, and self-consistent in that it can retrieve the solution directly from the compressed encoding, i.e. without ever passing through the expensive dense-vector representation. This machinery lays the foundations for a new generation of potentially radically more efficient solvers of real-life fluid problems.

We present a hybrid quantum-classical framework for simulating generic matrix functions more amenable to early fault-tolerant quantum hardware than standard quantum singular-value transformations. The method is based on randomization over the Chebyshev approximation of the target function while keeping the matrix oracle quantum, and is assisted by a variant of the Hadamard test that removes the need for post-selection. The resulting statistical overhead is similar to the fully quantum case and does not incur any circuit depth degradation. On the contrary, the average circuit depth is shown to get smaller, yielding equivalent reductions in noise sensitivity, as explicitly shown for depolarizing noise and coherent errors. We apply our technique to partition-function estimation, linear system solvers, and ground-state energy estimation. For these cases, we prove advantages on average depths, including quadratic speed-ups on costly parameters and even the removal of the approximation-error dependence., Comment: Accepted for publication in NPJ Quantum Information

A major obstacle for quantum optimizers is the reformulation of constraints as a quadratic unconstrained binary optimization (QUBO). Current QUBO translators exaggerate the weight $M$ of the penalty terms. Classically known as the "Big-$M$" problem, the issue becomes even more daunting for quantum solvers, since it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$ and establishing bounds on the Hamiltonian spectral gap $\Delta$, inversely related to the expected run-time of quantum solvers. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks. Our algorithm gives values of $\Delta$ orders of magnitude greater, e.g. for portfolio optimization instances. Solving such instances with an adiabatic algorithm on 6-qubits of an IonQ device, we observe significant advantages in time to solution and average solution quality. Our findings are relevant to quantum and quantum-inspired solvers alike., Comment: 11 pages, 3 figures

Implementing general functions of operators is a powerful tool in quantum computation. It can be used as the basis for a variety of quantum algorithms including matrix inversion, real and imaginary-time evolution, and matrix powers. Quantum signal processing is the state of the art for this aim, assuming that the operator to be transformed is given as a block of a unitary matrix acting on an enlarged Hilbert space. Here we present an algorithm for Hermitian-operator function design from an oracle given by the unitary evolution with respect to that operator at a fixed time. Our algorithm implements a Fourier approximation of the target function based on the iteration of a basic sequence of single-qubit gates, for which we prove the expressibility. In addition, we present an efficient classical algorithm for calculating its parameters from the Fourier series coefficients. Our algorithm uses only one qubit ancilla regardless the degree of the approximating series. This contrasts with previous proposals, which required an ancillary register of size growing with the expansion degree. Our methods are compatible with Trotterised Hamiltonian simulations schemes and hybrid digital-analog approaches., Comment: This paper formalizes and expands on a technique that we introduced in a summarized fashion in arXiv:2110.13180

Quantum error correction codes in continuous variables (also called CV codes, or single-mode bosonic codes) have recently been identified to be a technologically viable option for building fault-tolerant quantum computers. The best-known examples are the GKP code and the cat-code, both of which were shown to have some advantageous properties over any discrete-variable, or qubit codes. It was recently shown that the cat-code, as well as other kinds of CV codes, belong to a set of codes with common properties called rotation-symmetric codes. We expand this result by giving a general description of sets of codes with common properties, and rules by which they can be mapped into one another, effectively creating a unified description of continuous-variable codes. We prove that the properties of all of these sets of codes can be obtained from the properties of the GKP code. We also show explicitly how this construction works in the case of rotation-symmetric codes, re-deriving known properties and finding new ones., Comment: 22 pages (9 pages of main text and 13 pages of appendices), 2 figures, comments are welcome

High-connectivity circuits are a major roadblock for current quantum hardware. We propose a hybrid classical-quantum algorithm to simulate such circuits without swap-gate ladders. As main technical tool, we introduce quantum-classical-quantum interfaces. These replace an experimentally problematic gate (e.g. a long-range one) by single-qubit random measurements followed by state-preparations sampled according to a classical quasi-probability simulation of the noiseless gate. Each interface introduces a multiplicative statistical overhead which is remarkably independent of the on-chip qubit distance. Hence, by applying interfaces to the longest range gates in a target circuit, significant reductions in circuit depth and gate infidelity can be attained. We numerically show the efficacy of our method for a Bell-state circuit for two increasingly distant qubits and a variational ground-state solver for the transverse-field Ising model on a ring. Our findings provide a versatile toolbox for error-mitigation and circuit boosts tailored for noisy, intermediate-scale quantum computation.

As quantum technologies mature, the development of tools for benchmarking their ability to prepare and manipulate complex quantum states becomes increasingly necessary. A key concept, the state overlap between two quantum states, offers a natural tool to verify and cross-validate quantum simulators and quantum computers. Recent progress in controlling and measuring large quantum systems has motivated the development of state overlap estimators of varying efficiency and experimental complexity. Here, we demonstrate a practical approach for measuring the overlap between quantum states based on a factorable quasiprobabilistic representation of the states, and compare it with methods based on randomised measurements. Assuming realistic noisy intermediate scale quantum (NISQ) devices limitations, our quasiprobabilistic method outperforms the best circuits designed for state-overlap estimation for n-qubit states, with n > 2. For n < 7, our technique outperforms also the currently best direct estimator based on randomised local measurements, thus establishing a niche of optimality., Comment: 7 pages. Comments are welcome!

Simulating quantum imaginary-time evolution (QITE) is a major promise of quantum computation. However, the known algorithms are either probabilistic (repeat until success) with impractically small success probabilities or coherent (quantum amplitude amplification) but with circuit depths and ancillary-qubit numbers unrealistically large in the mid term. Our main contribution is a new generation of deterministic, high-precision QITE algorithms significantly more amenable experimentally. These are based on a surprisingly simple idea: partitioning the evolution into several fragments that are sequentially run probabilistically. This causes a huge reduction in wasted circuit depth every time a run fails. Indeed, the resulting overall runtime is asymptotically better than in coherent approaches and the hardware requirements even milder than in probabilistic ones, remarkably. More technically, we present two QITE-circuit sub-routines with excellent complexity scalings. One of them is optimal in ancillary-qubit overhead (one single ancillary qubit throughout) whereas the other one is optimal in runtime for small inverse temperature or high precision. The latter is shown by noting that the runtime saturates a cooling-speed limit that is the imaginary-time counterpart of the no fast-forwarding theorem of real-time simulations, which we prove. Moreover, we also make two technical contributions to the quantum signal processing formalism for operator-function synthesis (on which our sub-routines are based) that are useful beyond QITE. Our findings are specially relevant for the early fault-tolerance stages of quantum hardware., Comment: Full rigorous proof that fragmented QITE outperforms coherent QITE for general Hamiltonians added

The impressive pace of advance of quantum technology calls for robust and scalable techniques for the characterization and validation of quantum hardware. Quantum process tomography, the reconstruction of an unknown quantum channel from measurement data, remains the quintessential primitive to completely characterize quantum devices. However, due to the exponential scaling of the required data and classical post-processing, its range of applicability is typically restricted to one- and two-qubit gates. Here, we present a new technique for performing quantum process tomography that addresses these issues by combining a tensor network representation of the channel with a data-driven optimization inspired by unsupervised machine learning. We demonstrate our technique through synthetically generated data for ideal one- and two-dimensional random quantum circuits of up to 10 qubits, and a noisy 5-qubit circuit, reaching process fidelities above 0.99 using only a limited set of single-qubit measurement samples and input states. Our results go far beyond state-of-the-art, providing a practical and timely tool for benchmarking quantum circuits in current and near-term quantum computers., Comment: 16 pages, 10 figures

Models for quantum computation with circuit connections subject to the quantum superposition principle have been recently proposed. There, a control quantum system can coherently determine the order in which a target quantum system undergoes $N$ gate operations. This process, known as the quantum $N$-switch, is a resource for several information-processing tasks. In particular, it provides a computational advantage -- over fixed-gate-order quantum circuits -- for phase-estimation problems involving $N$ unknown unitary gates. However, the corresponding algorithm requires an experimentally unfeasible target-system dimension (super)exponential in $N$. Here, we introduce a promise problem for which the quantum $N$-switch gives an equivalent computational speed-up with target-system dimension as small as 2 regardless of $N$. We use state-of-the-art multi-core optical-fiber technology to experimentally demonstrate the quantum $N$-switch with $N=4$ gates acting on a photonic-polarization qubit. This is the first observation of a quantum superposition of more than $N=2$ temporal orders, demonstrating its usefulness for efficient phase-estimation., Comment: Main text: 9 pages, 3 figures; total 15 pages, 5 figures

The fundamental question of how to best simulate quantum systems using conventional computational resources lies at the forefront of condensed matter and quantum computation. It impacts both our understanding of quantum materials and our ability to emulate quantum circuits. Here we present an exact formulation of quantum dynamics via factorized generalized measurements which maps quantum states to probability distributions with the advantage that local unitary dynamics and quantum channels map to local quasi-stochastic matrices. This representation provides a general framework for using state-of-the-art probabilistic models in machine learning for the simulation of quantum many-body dynamics. Using this framework, we have developed a practical algorithm to simulate quantum circuits with the Transformer, a powerful ansatz responsible for the most recent breakthroughs in natural language processing. We demonstrate our approach by simulating circuits which build GHZ and linear graph states of up to 60 qubits, as well as a variational quantum eigensolver circuit for preparing the ground state of the transverse field Ising model on six qubits. Our methodology constitutes a modern machine learning approach to the simulation of quantum physics with applicability both to quantum circuits as well as other quantum many-body systems., Comment: 12 pages, 11 figures including supplementary materials

The study of stronger-than-quantum effects is a fruitful line of research that provides valuable insight into quantum theory. Unfortunately, traditional bipartite steering scenarios can always be explained by quantum theory. Here we show that, by relaxing this traditional setup, bipartite steering incompatible with quantum theory is possible. The two scenarios we describe, which still feature Alice remotely steering Bob's system, are: (i) one where Bob also has an input and operates on his subsystem, and (ii) the `instrumental steering' scenario. We show that such bipartite post-quantum steering is a genuinely new type of post-quantum nonlocality, which does not follow from post-quantum Bell nonlocality. In addition, we present a method to bound quantum violations of steering inequalities in these scenarios., Comment: 21 pages, one figure. Comments welcome ! V2: We include a relaxation (characterised by a semidefinite program) of the set of quantum assemblages in the Bob-with-Input scenario

The intrinsic random nature of quantum physics offers novel tools for the generation of random numbers, a central challenge for a plethora of fields. Bell non-local correlations obtained by measurements on entangled states allow for the generation of bit strings whose randomness is guaranteed in a device-independent manner, i.e. without assumptions on the measurement and state-generation devices. Here, we generate this strong form of certified randomness on a new platform: the so-called instrumental scenario, which is central to the field of causal inference. First, we theoretically show that certified random bits, private against general quantum adversaries, can be extracted exploiting device-independent quantum instrumental-inequality violations. To that end, we adapt techniques previously developed for the Bell scenario. Then, we experimentally implement the corresponding randomness-generation protocol using entangled photons and active feed-forward of information. Moreover, we show that, for low levels of noise, our protocol offers an advantage over the simplest Bell-nonlocality protocol based on the Clauser-Horn-Shimony-Holt inequality., Comment: Modified Supplementary Information: removed description of extractor algorithm introduced by arXiv:1212.0520. Implemented security of the protocol against general adversarial attacks

We study prepare-and-measure experiments where the sender (Alice) receives trusted quantum inputs but has an untrusted state-preparation device and the receiver (Bob) has a fully-untrusted measurement device. A distributed-sampling task naturally arises in such scenario, whose goal is for Alice and Bob to reproduce the statistics of his measurements on her quantum inputs using a fixed communication channel. Their performance at such task can certify quantum communication (QC), and this is formalised by measurement-device-independent QC witnesses. Furthermore, we prove that QC can provide an advantage (over classical communication) for distributed sampling if and only if Bob's measurements are incompatible. This gives an operational interpretation to the fundamental notion of measurement incompatibility, and motivates a generalised notion of it. Our findings have both fundamental and applied implications., Comment: 4+6 pages, 3 figures. v3: improved presentation and discussion on robustness

The first generation of multi-qubit quantum technologies will consist of noisy, intermediate-scale devices for which active error correction remains out of reach. To exploit such devices, it is thus imperative to use passive error protection that meets a careful trade-off between noise protection and resource overhead. Here, we experimentally demonstrate that single-qubit encoding can significantly enhance the robustness of entanglement and coherence of four-qubit graph states against local noise with a preferred direction. In particular, we explicitly show that local encoding provides a significant practical advantage for phase estimation in noisy environments. This demonstrates the efficacy of local unitary encoding under realistic conditions, with potential applications in multi-qubit quantum technologies for metrology, multi-partite secrecy and error correction., Comment: 7 figures

Causal nonseparability refers to processes where events take place in a coherent superposition of different causal orders. These may be the key resource for experimental violations of causal inequalities and have been recently identified as resources for concrete information-theoretic tasks. Here, we take a step forward by deriving a complete operational framework for causal nonseparability as a resource. Our first contribution is a formal definition of quantum control of causal orders, a stronger form of causal nonseparability (with the celebrated quantum switch as best-known example) where the causal orders of events for a target system are coherently controlled by a control system. We then build a resource theory -- for both generic causal nonseparability and quantum control of causal orders -- with a physically-motivated class of free operations, based on process-matrix concatenations. We present the framework explicitly in the mindset with a control register. However, our machinery is versatile, being applicable also to scenarios with a target register alone. Moreover, an important subclass of our operations not only is free with respect to causal nonseparability and quantum control of causal orders but also preserves the very causal structure of causal processes. Hence, our treatment contains, as a built-in feature, the basis of a resource theory of quantum causal networks too. As applications, first, we establish a sufficient condition for pure-process free convertibility. This imposes a hierarchy of quantum control of causal orders with the quantum switch at the top. Second, we prove that causal-nonseparability distillation exists, i.e. we show how to convert multiple copies of a process with arbitrarily little causal nonseparability into fewer copies of a quantum switch. Our findings reveal conceptually new, unexpected phenomena, with both fundamental and practical implications., Comment: Main text 11 pages, 3 figures, 20 pages total

We introduce witnesses for the average channel fidelity between a known target gate and an arbitrary unknown channel, for continuous-variable (CV) systems. These are observables whose expectation value yields a tight lower bound to the average channel fidelity in question, thus constituting a practical tool for certification of experimental CV gates. Our framework applies to a broad class of target gates. Here, we focus on three specific types of targets: multi-mode Gaussian unitary channels, single-mode coherent state amplifiers, and the single-mode (non-Gaussian) cubic phase gate, which is a crucial ingredient for CV universal quantum computation. Our witnesses are experimentally-friendly as they rely exclusively on Gaussian measurements, even for the non-Gaussian-target case. Moreover, in all three cases, they can be measured efficiently in the estimation error $\epsilon$ and failure probability $\Delta$, as well as in the number of modes $m$ for the Gaussian-target case. To end up with, our approach for the Gaussian-target case relies on an improved measurement scheme for Gaussian state-fidelity witnesses, which is polynomially and exponentially more efficient in $m$ and $\Delta$, respectively, than previous schemes. The latter constitutes an interesting byproduct result on its own. Our findings are relevant to the experimental validation of many-body quantum technologies., Comment: 15 pages

A major bottleneck in the quest for scalable many-body quantum technologies is the difficulty in benchmarking their preparations, which suffer from an exponential `curse of dimensionality' inherent to their quantum states. We present an experimentally friendly method for density matrix reconstruction based on deep neural-network generative models. The learning procedure comes with a built-in approximate certificate of the reconstruction and makes no assumptions on the state under scrutiny, making it both reliable and unconditional. It can efficiently handle a broad class of complex systems including prototypical states in quantum information, as well as ground states of local spin models common to condensed matter physics. The key insight is to reduce the state tomography task to an unsupervised learning problem of the statistics of an informationally complete set of quantum measurements. This constitutes a modern machine learning approach to the validation of large quantum devices, which may prove relevant as a neural-network ansatz over mixed states suitable for variational optimization., Comment: 29 pages, 9 figures. Includes appendix. Some typos in the description of the POVMs have been fixed. The numerically generated measurements, the implementation of the generative models, and the code to numerically generate the data sets used in this manuscript are available at https://github.com/carrasqu/POVM_GENMODEL

Inferring causal relations from experimental observations is of primal importance in science. Instrumental tests provide an essential tool for that aim, as they allow one to estimate causal dependencies even in the presence of unobserved common causes. In view of Bell's theorem, which implies that quantum mechanics is incompatible with our most basic notions of causality, it is of utmost importance to understand whether and how paradigmatic causal tools obtained in a classical setting can be carried over to the quantum realm. Here we show that quantum effects imply radically different predictions in the instrumental scenario. Among other results, we show that an instrumental test can be violated by entangled quantum states. Furthermore, we demonstrate such violation using a photonic set-up with active feed-forward of information, thus providing an experimental proof of this new form of non-classical behaviour. Our findings have fundamental implications in causal inference and may also lead to new applications of quantum technologies., Comment: Main manuscript (10 pages) + Supplementary Information (8 pages)

We present a verifiable and blind protocol for assisted universal quantum computing on continuous-variable (CV) platforms. This protocol is highly experimentally-friendly to the client, as it only requires Gaussian-operation capabilities from the latter. Moreover, the server is not required universal quantum-computational power either, its only function being to supply the client with copies of a single-mode non-Gaussian state. Universality is attained based on state-injection of the server's non-Gaussian supplies. The protocol is automatically blind because the non-Gaussian resource requested to the server is always the same, regardless of the specific computation. Verification, in turn, is possible thanks to an efficient non-Gaussian state fidelity test where we assume identical state preparation by the server. It is based on Gaussian measurements by the client on the injected states, which is potentially interesting on its own. The division of quantum hardware between client and server assumed here is in agreement with the experimental constraints expected in realistic schemes for CV cloud quantum computing.

Supraquantum nonlocality refers to correlations that are more nonlocal than allowed by quantum theory but still physically conceivable in post-quantum theories, in the sense of respecting the basic no-faster-than-light communication principle. While supraquantum correlations are relatively well understood for finite-dimensional systems, little is known in the infinite-dimensional case. Here, we study supraquantum nonlocality for bipartite systems with two measurement settings and infinitely many outcomes per subsystem. We develop a formalism for generic no-signaling black-box measurement devices with continuous outputs in terms of probability measures, instead of probability distributions, which involves a few technical subtleties. We show the existence of a class of supraquantum Gaussian correlations, which violate the Tsirelson bound of an adequate continuous-variable Bell inequality. We then introduce the continuous-variable version of the celebrated Popescu-Rohrlich (PR) boxes, as a limiting case of the above-mentioned Gaussian ones. Finally, we perform a characterisation of the geometry of the set of continuous-variable no-signaling correlations. Namely, we show that that the convex hull of the continuous-variable PR boxes is dense in the no-signaling set. We also show that these boxes are extreme in the set of no-signaling behaviours and provide evidence suggesting that they are indeed the only extreme points of the no-signaling set. Our results lay the grounds for studying generalized-probability theories in continuous-variable systems., Comment: 10 pages, 3 figures, minor improvements and corrected typos

Contextuality is a fundamental feature of quantum theory and is necessary for quantum computation and communication. Serious steps have therefore been taken towards a formal framework for contextuality as an operational resource. However, the most important component for a resource theory - a concrete, explicit form for the free operations of contextuality - was still missing. Here we provide such a component by introducing noncontextual wirings: a physically-motivated class of contextuality-free operations with a friendly parametrization. We characterize them completely for the general case of black-box measurement devices with arbitrarily many inputs and outputs. As applications, we show that the relative entropy of contextuality is a contextuality monotone and that maximally contextual boxes that serve as contextuality bits exist for a broad class of scenarios. Our results complete a unified resource-theoretic framework for contextuality and Bell nonlocality.

Bell nonlocality can be formulated in terms of a resource theory with local-hidden variable models as resourceless objects. Two such theories are known, one built upon local operations assisted by shared randomness (LOSRs) and the other one allowing, in addition, for prior-to-input classical communication. We show that prior communication, although unable to create nonlocality, leads to wirings not only beyond LOSRs but also not contained in a much broader class of (nonlocality-generating) global wirings. Technically, this is shown by proving that it can improve the statistical distinguishability between Bell correlations optimised over all fixed measurement choices. This has implications in nonlocality quantification, and leads us to a natural universal definition of Bell nonlocality measures. To end up with, we also consider the statistical strength of nonlocality proofs. We point out some issues of its standard definition in the resource-theoretic operational framework, and suggest simple fixes for them. Our findings reveal non-trivial features of the geometry of the set of wirings and may have implications in the operational distinguishability of nonlocal behaviors., Comment: 15 pages, 2 figures. Typos corrected and some proofs simplified

As with entanglement, different forms of Bell nonlocality arise in the multipartite scenario. These can be defined in terms of relaxations of the causal assumptions in local hidden-variable theories. However, a characterisation of all the forms of multipartite nonlocality has until now been out of reach, mainly due to the complexity of generic multipartite causal models. Here, we employ the formalism of Bayesian networks to reveal connections among different causal structures that make a both practical and physically meaningful classification possible. Our framework holds for arbitrarily many parties. We apply it to study the tripartite scenario in detail, where we fully characterize all the nonlocality classes. Remarkably, we identify new highly nonlocal causal structures that cannot reproduce all quantum correlations. This shows, to our knowledge, the strongest form of quantum multipartite nonlocality known to date. Finally, as a by-product result, we derive a non-trivial Bell-type inequality with no quantum violation. Our findings constitute a significant step forward in the understanding of multipartite Bell nonlocality and open several venues for future research., Comment: 6 pages + appendix, 3 figures, 3 tables. Minor errors corrected, discovery of strongest form of quantum multipartite non-locality known so far added. v3: text improved. v4: Accepted by Quantum

Quantum steering is observed when performing appropriate local measurements on an entangled state. Here we discuss the possibility of simulating classically this effect, using classical communication instead of entanglement. We show that infinite communication is necessary for exactly simulating steering for any pure entangled state, as well as for a class of mixed entangled states. Moreover, we discuss the communication cost of steering for general entangled states, as well as approximate simulation. Our findings reveal striking differences between Bell nonlocality and steering, and provide a natural way of measuring the strength of the latter., Comment: 7 pages, 1 figure. See also arXiv:1603.xxxxx for related work by S. Nagy and T. V\'ertesi

Recent schemes to encode quantum information into the total angular momentum of light, defining rotation-invariant hybrid qubits composed of the polarization and orbital angular momentum degrees of freedom, present interesting applications for quantum information technology. However, there remains the question as to how detrimental effects such as random spatial perturbations affect these encodings. Here, we demon- strate that alignment-free quantum communication through a turbulent channel based on hybrid qubits can be achieved with unit transmission fidelity. In our experiment, alignment-free qubits are produced with q-plates and sent through a homemade tur- bulence chamber. The decoding procedure, also realized with q-plates, relies on both degrees of freedom and renders an intrinsic error-filtering mechanism that maps errors into losses., Comment: 9 pages, 7 figures. published in Scientific Reports

We present an operational framework for Einstein-Podolsky-Rosen steering as a physical resource. To begin with, we characterize the set of steering non-increasing operations (SNIOs) --i.e., those that do not create steering-- on arbitrary-dimensional bipartite systems composed of a quantum subsystem and a black-box device. Next, we introduce the notion of convex steering monotones as the fundamental axiomatic quantifiers of steering. As a convenient example thereof, we present the relative entropy of steering. In addition, we prove that two previously proposed quantifiers, the steerable weight and the robustness of steering, are also convex steering monotones. To end up with, for minimal-dimensional systems, we establish, on the one hand, necessary and sufficient conditions for pure-state steering conversions under stochastic SNIOs and prove, on the other hand, the non-existence of steering bits, i.e., measure-independent maximally steerable states from which all states can be obtained by means of the free operations. Our findings reveal unexpected aspects of steering and lay foundations for further resource-theory approaches, with potential implications in Bell non-locality., Comment: Presentation and structure improved

One of the greatest challenges in quantum information processing is the coherent control over quantum systems with an ever increasing number of particles. Within this endeavor, the harnessing of many-body entanglement against the effects of the environment is a pressing issue. Besides being an important concept from a fundamental standpoint, entanglement is recognized as a crucial resource for performance enhancements over classical methods. Understanding and controlling many-body entanglement in open systems may have implications in quantum computing, quantum simulations, secure quantum communication, quantum metrology, our understanding of the quantum-to-classical transition, and other important questions of quantum foundations. Here we present an overview of recent theoretical and experimental efforts to underpin the dynamics of entanglement in open quantum systems. Entanglement is taken as a dynamic quantity, and we survey how it evolves due to the interaction of the entangled system with its surroundings. We analyze several scenarios, corresponding to different families of states and environments, which render a diversity of dynamical behaviors. Contrary to single-particle quantities, that typically vanish only asymptotically in time, entanglement may disappear at a finite time. Moreover, important classes of entanglement show an exponential decay with the system size when subject to local noise, posing yet another threat to the already challenging scaling of quantum technologies. Results for the local and global noise cases are summarized. Robustness-enhancement techniques, scaling laws, statistical and geometrical aspects of multipartite-entanglement decay are also reviewed; all in order to give a broad picture of entanglement dynamics in open quantum systems addressed to both theorists and experimentalists inside and outside the field of quantum information., Comment: 76 pages, 32 figures. Long-overdue review article. Preliminary version. Comments are very welcome

The Clauser-Horne-Shimony-Holt inequality was originally proposed as a Bell inequality to detect nonlocality in bipartite systems. However, it can also be used to certify the nonlocality of multipartite quantum states. We apply this to study the nonlocality of multipartite Greenberger-Horne-Zeilinger, W and graph states under local decoherence processes. We derive lower bounds on the critical local-noise strength tolerated by GHZ states before becoming local. In addition, for the whole noisy dynamics, we derive lower bounds on the corresponding nonlocal content for the three classes of states. All the bounds presented can be calculated efficiently and, in some cases, provide significantly tighter estimates than with any other known method. For example, they reveal that $N$-qubit GHZ states undergoing local dephasing are, for all $N$, nonlocal throughout all the dephasing dynamics., Comment: 8 pages, 3 figures

Do completely unpredictable events exist in nature? Classical theory, being fully deterministic, completely excludes fundamental randomness. On the contrary, quantum theory allows for randomness within its axiomatic structure. Yet, the fact that a theory makes prediction only in probabilistic terms does not imply the existence of any form of randomness in nature. The question then remains whether one can certify randomness independent of the physical framework used. While standard Bell tests approach this question from this perspective, they require prior perfect randomness, which renders the approach circular. Recently, it has been shown that it is possible to certify full randomness using almost perfect random bits. Here, we prove that full randomness can indeed be certified using quantum non-locality under the minimal possible assumptions: the existence of a source of arbitrarily weak (but non-zero) randomness and the impossibility of instantaneous signalling. Thus we are left with a strict dichotomic choice: either our world is fully deterministic or there exist in nature events that are fully random. Apart from the foundational implications, our results represent a quantum protocol for full randomness amplification, an information task known to be impossible classically. Finally, they open a new path for device-independent protocols under minimal assumptions., Comment: 4 pages, 2 figures + appendices

We describe a simple entangling principle based on the scattering of photons off single emitters in one-dimensional waveguides (or extremely-lossy cavities). The scheme can be applied to photonic qubits encoded in polarization or time-bin, and features a filtering mechanism that works effectively as a built-in error-correction directive. This automatically maps imperfections from weak couplings, atomic decay into undesired modes, frequency mismatches, or finite bandwidths of the incident photonic pulses, into heralded losses instead of infidelities. The scheme is thus adequate for high-fidelity maximally entangling gates even in the weak-coupling regime. These, in turn, can be directly applied to store and retrieve photonic-qubit states, thereby completing an atom-photon interface toolbox, or to sequential measurement-based quantum computations with atomic memories., Comment: 5 pages, 2 figures

We study the nonlocal properties of two-qubit maximally-entangled and N-qubit Greenberger-Horne-Zeilinger states under local decoherence. We show that the (non)resilience of entanglement under local depolarization or dephasing is not necessarily equivalent to the (non)resilience of Bell-inequality violations. Apart from entanglement and Bell-inequality violations, we consider also nonlocality as quantified by the nonlocal content of correlations, and provide several examples of anomalous behaviors, both in the bipartite and multipartite cases. In addition, we study the practical implications of these anomalies on the usefulness of noisy Greenberger-Horne-Zeilinger states as resources for nonlocality-based physical protocols given by communication complexity problems. There, we provide examples of quantum gains improving with the number of particles that coexist with exponentially-decaying entanglement and non-local contents., Comment: 6 pages, 4 figures

Quantum communication employs the counter-intuitive features of quantum physics to perform tasks that are im- possible in the classical world. It is crucial for testing the foundations of quantum theory and promises to rev- olutionize our information and communication technolo- gies. However, for two or more parties to execute even the simplest quantum transmission, they must establish, and maintain, a shared reference frame. This introduces a considerable overhead in communication resources, par- ticularly if the parties are in motion or rotating relative to each other. We experimentally demonstrate how to circumvent this problem with the efficient transmission of quantum information encoded in rotationally invariant states of single photons. By developing a complete toolbox for the efficient encoding and decoding of quantum infor- mation in such photonic qubits, we demonstrate the fea- sibility of alignment-free quantum key-distribution, and perform a proof-of-principle alignment-free entanglement distribution and violation of a Bell inequality. Our scheme should find applications in fundamental tests of quantum mechanics and satellite-based quantum communication., Comment: Main manuscript: 7 pages, 3 figures; Supplementary Information: 7 pages, 3 figures

One of the main challenges for the manipulation and storage of multipartite entanglement is its fragility under noise. We present a simple recipe for the systematic enhancement of the resistance of multipartite entanglement against any local noise with a privileged direction in the Bloch sphere. For the case of exact local dephasing along any given basis, and for all noise strengths, our prescription grants full robustness: Even states with exponentially decaying entanglement are mapped to states whose entanglement is constant. In contrast to previous techniques resorting to complex logical-qubit encodings, such enhancement is attained simply by performing local-unitary rotations before the noise acts. The scheme is therefore highly experimentally friendly, as it brings no overhead of extra physical qubits to encode logical ones. In addition, we show that, apart from entanglement, the resiliences of the relative entropy of quantumness and the usefulness as resources for practical tasks such as metrology and nonlocality-based protocols are equivalently enhanced., Comment: 4 pages + appendix, 3 figures

Local measurements on bipartite maximally entangled states can yield correlations that are maximally nonlocal, monogamous, and associated to fully random outcomes. This makes these states ideal for bipartite cryptographic tasks. Genuine-multipartite nonlocality constitutes a stronger notion of nonlocality that appears in the multipartite case. Maximal genuine-multipartite nonlocality, monogamy and full random outcomes are thus highly desired properties for multipartite correlations in intrinsically genuine-multipartite cryptographic scenarios. We prove that local measurements on Greenberger-Horne-Zeilinger states, for all local dimension and number of parts, can produce correlations that are fully genuine-multipartite nonlocal, monogamous and with fully random outcomes. A key ingredient in our proof is a multipartite chained Bell inequality detecting genuine-multipartite nonlocality, which we introduce. Finally, we discuss the applications of our results for intrinsically genuine-multipartite cryptographic protocols such as device-independent secret sharing., Comment: 5 + 2 and 1/2 pages. To appear in PRL

Quantum mechanics is a nonlocal theory, but not as nonlocal as the no-signalling principle allows. However, there exist quantum correlations that exhibit maximal nonlocality: they are as nonlocal as any non-signalling correlations and thus have a local content, quantified by the fraction $p_L$ of events admitting a local description, equal to zero. Exploiting the link between the Kochen-Specker and Bell's theorems, we derive, from every Kochen-Specker proof, Bell inequalities maximally violated by quantum correlations. We then show that these Bell inequalities lead to experimental bounds on the local content of quantum correlations which are significantly better than those based on other constructions. We perform the experimental demonstration of a Bell test originating from the Peres-Mermin Kochen-Specker proof, providing an upper bound on the local content $p_L\lesssim 0.22$., Comment: 9 pages, 5 figures and three tables. To appear in PRA

We introduce a general scheme for sequential one-way quantum computation where static systems with long-living quantum coherence (memories) interact with moving systems that may possess very short coherence times. Both the generation of the cluster state needed for the computation and its consumption by measurements are carried out simultaneously. As a consequence, effective clusters of one spatial dimension fewer than in the standard approach are sufficient for computation. In particular, universal computation requires only a one-dimensional array of memories. The scheme applies to discrete-variable systems of any dimension as well as to continuous-variable ones, and both are treated equivalently under the light of local complementation of graphs. In this way our formalism introduces a general framework that encompasses and generalizes in a unified manner some previous system-dependent proposals. The procedure is intrinsically well-suited for implementations with atom-photon interfaces., Comment: 6 pages, 4 figures

We introduce a family of Hamiltonian systems for measurement-based quantum computation with continuous variables. The Hamiltonians (i) are quadratic, and therefore two body, (ii) are of short range, (iii) are frustration-free, and (iv) possess a constant energy gap proportional to the squared inverse of the squeezing. Their ground states are the celebrated Gaussian graph states, which are universal resources for quantum computation in the limit of infinite squeezing. These Hamiltonians constitute the basic ingredient for the adiabatic preparation of graph states and thus open new venues for the physical realization of continuous-variable quantum computing beyond the standard optical approaches. We characterize the correlations in these systems at thermal equilibrium. In particular, we prove that the correlations across any multipartition are contained exactly in its boundary, automatically yielding a correlation area law., Comment: 4 pages, one figure. New version: typos corrected, one reference added. To appear in PRL

We propose a protocol for the creation of photonic Greenberger-Horne-Zeilinger and linear cluster states emitted from a single atom---or ion---coupled to an optical cavity field. The method is based on laser pulses with different polarizations and exploits the atomic transition amplitudes to state-selectively achieve the desired transitions. The scheme lies within reach of current technology., Comment: Six pages, two figures. Two appendices (including discussion about error sources). To appear in PRA