Search

A major obstacle towards practical quantum optimizations is the reformulation of constrained problems as a quadratic unconstrained binary optimization (QUBO). Existing QUBO translators significantly over-estimate the weight $M$ of the penalization terms. This issue, known as the "Big-$M$" problem in classical optimization, becomes even more daunting for quantum solvers, since it affects the physical energy scale. We develop a theory of the quantum big-$M$ problem. We observe that finding the optimal $M$ is NP-hard and establish relevant upper bounds on the Hamiltonian spectral gap $\Delta$, formalizing the intuition that $\Delta=\mathcal{O}(M^{-1})$. Most importantly, we deliver a practical QUBO-reformulation algorithm based on the SDP relaxation. Numerical benchmarks show an impressive out-performance over previous methods. In particular, for portfolio optimization (PO) instances of up to 24 qubits, our algorithm gives values of $M$ ($\Delta$) orders of magnitude smaller (greater). Additionally, we experimentally solve 6-qubit PO instances with an approximately adiabatic algorithm on an IonQ device. There, we observe a remarkable advantage both in the probability of right solution and in the average solution quality. Our findings are relevant not only to current and near-term quantum but also quantum-inspired solvers.

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

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., Full rigorous proof that fragmented QITE outperforms coherent QITE for general Hamiltonians added

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., 7 pages. Comments are welcome!

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., 12 pages, 11 figures including supplementary materials

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., 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

We derive analytical upper bounds for the entanglement of generalized Greenberger-Horne-Zeilinger states coupled to locally depolarizing and dephasing environments, and for local thermal baths of arbitrary temperature. These bounds apply for any convex quantifier of entanglement, and exponential entanglement decay with the number of constituent particles is found. The bounds are tight for depolarizing and dephasing channels. We also show that randomly generated initial states tend to violate these bounds, and that this discrepancy grows with the number of particles., Comment: 9 pages, 3 figures