Top arXiv papers

sign in to customize
  • PDF
    We introduce a distributed classical simulation algorithm for general quantum circuits, and present numerical results for calculating the output probabilities of universal random circuits. We find that we can simulate more qubits to greater depth than previously reported using the cluster supported by the Data Infrastructure and Search Technology Division of the Alibaba Group. For example, computing a single amplitude of an $8\times 8$ qubit circuit with depth $40$ was previously beyond the reach of supercomputers. Our algorithm can compute this within $2$ minutes using a small portion ($\approx$ 14% of the nodes) of the cluster. Furthermore, by successfully simulating quantum supremacy circuits of size $9\times 9\times 40$, $10\times 10\times 35 $, $11\times 11\times 31$, and $12\times 12\times 27 $, we give evidence that noisy random circuits with realistic physical parameters may be simulated classically. This suggests that either harder circuits or error-correction may be vital for achieving quantum supremacy from random circuit sampling.
  • PDF
    Quantum computational supremacy arguments, which describe a way for a quantum computer to perform a task that cannot also be done by a classical computer, require some sort of computational assumption related to the limitations of classical computation. One common assumption is that the polynomial hierarchy (PH) does not collapse, a stronger version of the statement that P $\neq$ NP, which leads to the conclusion that any classical simulation of certain families of quantum circuits requires more than polynomial time in the size of the circuits. However, the asymptotic nature of this conclusion prevents us from calculating exactly how many qubits these quantum circuits must have for their classical simulation to be intractable on modern classical supercomputers. We refine these quantum computational supremacy arguments and perform such a calculation by imposing a fine-grained version of the non-collapse assumption, which we argue is still plausible. Under the fine-grained assumption, we conclude that Instantaneous Quantum Polynomial-Time (IQP) circuits with 90 qubits, Quantum Approximate Optimization Algorithm (QAOA) circuits with 180 qubits, or boson sampling circuits (i.e. linear optical networks) with 90 photons, are large enough for the task of producing samples from their output distributions up to constant multiplicative error to be intractable on current technology.
  • PDF
    A self-correcting quantum memory can store and protect quantum information for a time that increases without bound with the system size, without the need for active error correction. We demonstrate that symmetry can lead to self-correction in 3D spin lattice models. In particular, we investigate codes given by 2D symmetry-enriched topological (SET) phases that appear naturally on the boundary of 3D symmetry protected topological (SPT) phases. We find that while conventional onsite symmetries are not sufficient to allow for self-correction in commuting Hamiltonian models of this form, a generalized type of symmetry known as a 1-form symmetry is enough to guarantee self-correction. We illustrate this fact with the 3D `cluster state' model from the theory of quantum computing. This model is a self-correcting memory, where information is encoded in a 2D SET ordered phase on the boundary that is protected by the thermally stable SPT ordering of the bulk. We also investigate the gauge color code in this context. Finally, noting that a 1-form symmetry is a very strong constraint, we argue that topologically ordered systems can possess emergent 1-form symmetries, i.e., models where the symmetry appears naturally, without needing to be enforced externally.
  • PDF
    Machine learning and quantum computing are two technologies each with the potential for altering how computation is performed to address previously untenable problems. Kernel methods for machine learning are ubiquitous for pattern recognition, with support vector machines (SVMs) being the most well-known method for classification problems. However, there are limitations to the successful solution to such problems when the feature space becomes large, and the kernel functions become computationally expensive to estimate. A core element to computational speed-ups afforded by quantum algorithms is the exploitation of an exponentially large quantum state space through controllable entanglement and interference. Here, we propose and use two novel methods which represent the feature space of a classification problem by a quantum state, taking advantage of the large dimensionality of quantum Hilbert space to obtain an enhanced solution. One method, the quantum variational classifier builds on [1,2] and operates through using a variational quantum circuit to classify a training set in direct analogy to conventional SVMs. In the second, a quantum kernel estimator, we estimate the kernel function and optimize the classifier directly. The two methods present a new class of tools for exploring the applications of noisy intermediate scale quantum computers to machine learning.
  • PDF
    We develop the procedures of gauging and ungauging, reveal their operational meaning and propose their generalization in a systematic manner within the framework of quantum error-correcting codes. We demonstrate with an example of the subsystem Bacon-Shor code that the ungauging procedure can result in models with unusual symmetry operators constrained to live on lower-dimensional structures. We apply our formalism to the three-dimensional gauge color code (GCC) and show that its codeword space is equivalent to the Hilbert space of six copies of $\mathbb{Z}_2$ lattice gauge theory with $1$-form symmetries. We find that three different stabilizer Hamiltonians associated with the GCC correspond to distinct thermal symmetry-protected topological (SPT) phases in the presence of the stabilizer symmetries of the GCC. One of the considered Hamiltonians describes the Raussendorf-Bravyi-Harrington model, which is universal for measurement-based quantum computation at non-zero temperature. We also propose a general procedure of creating $D$-dimensional SPT Hamiltonians from $(D+1)$-dimensional CSS stabilizer Hamiltonians by exploiting a relation between gapped domain walls and transversal logical gates. As a result, we find an explicit two-dimensional realization of a non-trivial fracton SPT phase protected by fractal-like symmetries.
  • PDF
    We consider the problem of strong (amplitude-wise) simulation of $n$-qubit quantum circuits, and identify a subclass of simulators we call monotone. This subclass encompasses almost all prominent simulation techniques. We prove an unconditional (i.e. without relying on any complexity theoretic assumptions) and explicit $(n-2)(2^{n-3}-1)$ lower bound on the running time of simulators within this subclass. Assuming the Strong Exponential Time Hypothesis (SETH), we further remark that a universal simulator computing any amplitude to precision $2^{-n}/2$ must take at least $2^{n - o(n)}$ time. Finally, we compare strong simulators to existing SAT solvers, and identify the time-complexity below which a strong simulator would improve on state-of-the-art SAT solving.
  • PDF
    An important family of span programs, st-connectivity span programs, have been used to design quantum algorithms in various contexts, including a number of graph problems and formula evaluation problems. The complexity of the resulting algorithms depends on the largest positive witness size of any 1-input, and the largest negative witness size of any 0-input. Belovs and Reichardt first showed that the positive witness size is exactly characterized by the effective resistance of the input graph, but only rough upper bounds were known previously on the negative witness size. We show that the negative witness size in an st-connectivity span program is exactly characterized by the capacitance of the input graph. This gives a tight analysis for algorithms based on st-connectivity span programs on any set of inputs. We use this analysis to give a new quantum algorithm for estimating the capacitance of a graph. We also describe a new quantum algorithm for deciding if a graph is connected, which improves the previous best quantum algorithm for this problem if we're promised that either the graph has at least kappa > 1 components, or the graph is connected and has small average resistance, which is upper bounded by the diameter. We also give an alternative algorithm for deciding if a graph is connected that can be better than our first algorithm when the maximum degree is small. Finally, using ideas from our second connectivity algorithm, we give an algorithm for estimating the algebraic connectivity of a graph, the second largest eigenvalue of the Laplacian.
  • PDF
    Stabilizer states form an important class of states in quantum information, and are of central importance in quantum error correction. Here, we provide an algorithm for deciding whether one stabilizer (target) state can be obtained from another stabilizer (source) state by single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM), and classical communication (CC) between sites holding the individual qubits. What's more, we provide a recipe to obtain the sequence of LC+LPM+CC operations which prepare the desired target state from the source state, and show how these operations can be applied in parallel to reach the target state in constant time. Our algorithm has applications in quantum networks, quantum computing, and can also serve as a design tool - for example, to find transformations between quantum error correcting codes. We provide a software implementation of our algorithm that makes this tool easier to apply. A key insight leading to our algorithm is to show that the problem is equivalent to one in graph theory, which is to decide whether some graph G' is a vertex-minor of another graph G. Here we show that the vertex-minor problem can be solved in time O(|G|^3) where |G| is the size of the graph G, whenever the rank-width of G and the size of G' are bounded. Our algorithm is based on techniques by Courcelle for solving fixed parameter tractable problems, where here the relevant fixed parameter is the rank width. The second half of this paper serves as an accessible but far from exhausting introduction to these concepts, that could be useful for many other problems in quantum information.
  • PDF
    It is often the case in quantum Hamiltonian complexity (e.g. in the context of quantum simulations, adiabatic algorithms, perturbative gadgets and quantum NP theory) that one is mainly interested in the properties of the groundstate(s) of a Hamiltonian, and not in the rest of the spectrum. We capture this situation using a notion we call gap-simulation and initiate the study of the resources required for gap-simulating a Hamiltonian $H$ by a Hamiltonian $\tilde{H}$. In particular we focus on two notions: degree-reduction and dilution. In degree-reduction, one aims to simulate a high degree Hamiltonian $H$ by a constant degree Hamiltonian $\tilde{H}$; whereas in dilution, the total number of edges (interactions) is reduced. Our main result is a proof that unlike in the classical case, general quantum degree-reduction is impossible. We provide two example Hamiltonians $H_A$ and $H_B$, and show, using an adaptation of Hastings-Koma decay of correlation, that no bounded degree Hamiltonian with bounded-norm terms (i.e. bounded interaction strength) can gap-simulate these Hamiltonians. We further establish several possibility results if one relaxes some of the requirements such as the norm of the individual terms, or the coherence of the gap-simulation. Finally, we connect these impossibility results to the attempt to construct quantum PCP reductions, and provide partial impossibility results of degree-reduction in this context as well. We believe that this work leads to a rich set of new questions in quantum Hamiltonian complexity.
  • PDF
    We construct quantum circuits which exactly encode the spectra of correlated electron models up to errors from rotation synthesis. By invoking these circuits as oracles within the recently introduced "qubitization" framework, one can use quantum phase estimation to sample states in the Hamiltonian eigenbasis with optimal query complexity $O(\lambda / \epsilon)$ where $\lambda$ is an absolute sum of Hamiltonian coefficients and $\epsilon$ is target precision. For both the Hubbard model and electronic structure Hamiltonian in a second quantized basis diagonalizing the Coulomb operator, our circuits have T gate complexity $O({N + \log (1/\epsilon}))$ where $N$ is number of orbitals in the basis. Compared to prior approaches, our algorithms are asymptotically more efficient in gate complexity and require fewer T gates near the classically intractable regime. Compiling to surface code fault-tolerant gates and assuming per gate error rates of one part in a thousand reveals that one can error correct phase estimation on interesting instances of these problems beyond the current capabilities of classical methods using only about one million superconducting qubits in a matter of hours.
  • PDF
    We present a low-space overhead simulation algorithm based on the truncated Dyson series for time-dependent quantum dynamics. This algorithm is applied to simulating time-independent Hamiltonians by transitioning to the interaction picture, where some portions are made time-dependent. This can provide a favorable complexity trade-off as the algorithm scales exponentially better with derivatives of the time-dependent component than the original Hamiltonian. We show that this leads to an exponential improvement in gate complexity for simulating some classes of diagonally dominant Hamiltonian. Additionally we show that this can reduce the gate-complexity scaling for simulating $N$-site Hubbard models for time $t$ with arbitrary long-range interactions as well as reduce the cost of quantum chemistry simulations within a similar-sized plane-wave basis to $\widetilde{\mathcal{O}}(N^2t)$ from $\widetilde{\mathcal{O}}(N^{11/3}t)$. We also show a quadratic improvement in query complexity for simulating sparse time-dependent Hamiltonians, which may be of independent interest.
  • PDF
    Contextuality - the inability to assign pre-existing outcomes to all potential measurements of a quantum system - has been proposed as a resource that powers quantum computing. The measurement-based model provides a concrete manifestation of contextuality as a computational resource, as follows. If local measurements on a multi-qubit state can be used to evaluate non-linear boolean functions with only linear control processing, then this computation constitutes a proof of contextuality - the possible local measurement outcomes cannot all be pre-assigned. However, this connection is restricted to the special case when the local measured systems are qubits, which have unusual properties from the perspective of contextuality. A single qubit cannot allow for a proof of contextuality, unlike higher-dimensional systems, and multiple qubits can allow for state-independent contextuality with only Pauli observables, again unlike higher-dimensional generalisations. Here we identify precisely which non-local features of contextuality are necessary in a qudit measurement-based computation that evaluates high-degree polynomial functions with only linear control. We introduce the concept of local universality, which places a bound on the space of output functions accessible under the constraint of single-qudit measurements. Thus, the partition of a physical system into subsystems plays a crucial role for the increase in computational power. A prominent feature of our setting is that the enabling resources for qubit and qudit measurement-based computations are of the same underlying nature, avoiding the pathologies associated with qubit contextuality.
  • PDF
    We reconsider the basic building blocks of classical phenomenological thermodynamics. While doing so we show that the zeroth law is a redundant postulate for the theory by deriving it from the first and the second laws. This is in stark contrast to the prevalent conception that the three laws, the zeroth, first and second, are all necessary and independent axioms.
  • PDF
    The no-programming theorem prohibits the existence of a Universal Programmable Quantum Processor. This statement has several implications in relation to quantum computation, but also to other tasks of quantum information processing, making this construction a central notion in this context. Nonetheless, it is well known that even when the strict model is not implementable, it is possible to conceive of it in an approximate sense. Unfortunately, the minimal resources necessary for this aim are still not completely understood. Here, we investigate quantitative statements of the theorem, improving exponentially previous bounds on the resources required by such a hypothetical machine. The proofs exploit a new connection between quantum channels and embeddings between Banach spaces which allows us to use classical tools from geometric Banach space theory in a clean and simple way.
  • PDF
    Generative adversarial networks (GANs) represent a powerful tool for classical machine learning: a generator tries to create statistics for data that mimics those of a true data set, while a discriminator tries to discriminate between the true and fake data. The learning process for generator and discriminator can be thought of as an adversarial game, and under reasonable assumptions, the game converges to the point where the generator generates the same statistics as the true data and the discriminator is unable to discriminate between the true and the generated data. This paper introduces the notion of quantum generative adversarial networks (QuGANs), where the data consists either of quantum states, or of classical data, and the generator and discriminator are equipped with quantum information processors. We show that the unique fixed point of the quantum adversarial game also occurs when the generator produces the same statistics as the data. Since quantum systems are intrinsically probabilistic the proof of the quantum case is different from - and simpler than - the classical case. We show that when the data consists of samples of measurements made on high-dimensional spaces, quantum adversarial networks may exhibit an exponential advantage over classical adversarial networks.
  • PDF
    Quantum computation appears to offer significant advantages over classical computation and this has generated a tremendous interest in the field. In this thesis we consider the application of quantum computers to scientific computing and combinatorial optimization. We study five problems. The first three deal with quantum algorithms for computational problems in science and engineering, including quantum simulation of physical systems. In particular, we study quantum algorithms for numerical computation, for the approximation of ground and excited state energies of the Schrödinger equation, and for Hamiltonian simulation with applications to physics and chemistry. The remaining two deal with quantum algorithms for approximate optimization. We study the performance of the quantum approximate optimization algorithm (QAOA), and show a generalization of QAOA, the $\textit{quantum}$ $\textit{alternating}$ $\textit{operator}$ $\textit{ansatz}$, particularly suitable for constrained optimization problems and low-resource implementations on near-term quantum devices.
  • PDF
    The role of coherence in quantum thermodynamics has been extensively studied in the recent years and it is now well-understood that coherence between different energy eigenstates is a resource independent of other thermodynamics resources, such as work. A fundamental remaining open question is whether the laws of quantum mechanics and thermodynamics allow the existence a "coherence distillation machine", i.e. a machine that, by possibly consuming work, obtains pure coherent states from mixed states, at a nonzero rate. This question is related to another fundamental question: Starting from many copies of noisy quantum clocks which are (approximately) synchronized with a reference clock, can we distill synchronized clocks in pure states, at a non-zero rate? In this paper we study quantities called "coherence cost" and "distillable coherence", which determine the rate of conversion of coherence in a standard pure state to general mixed states, and vice versa, in the context of quantum thermodynamics. We find that the coherence cost of any state (pure or mixed) is determined by its Quantum Fisher Information (QFI), thereby revealing a novel operational interpretation of this central quantity of quantum metrology. On the other hand, we show that, surprisingly, distillable coherence is zero for typical (full-rank) mixed states. Hence, we establish the impossibility of coherence distillation machines in quantum thermodynamics, which can be compared with the impossibility of perpetual motion machines or cloning machines. To establish this result, we introduce a new additive quantifier of coherence, called the "purity of coherence", and argue that its relation with QFI is analogous to the relation between the free and total energies in thermodynamics.
  • PDF
    Quantum computation, a completely different paradigm of computing, benefits from theoretically proven speed-ups for certain problems and opens up the possibility of exactly studying the properties of quantum systems. Yet, because of the inherent fragile nature of the physical computing elements, qubits, achieving quantum advantages over classical computation requires extremely low error rates for qubit operations as well as a significant overhead of physical qubits, in order to realize fault-tolerance via quantum error correction. However, recent theoretical work has shown that the accuracy of computation based off expectation values of quantum observables can be enhanced through an extrapolation of results from a collection of varying noisy experiments. Here, we demonstrate this error mitigation protocol on a superconducting quantum processor, enhancing its computational capability, with no additional hardware modifications. We apply the protocol to mitigate errors on canonical single- and two-qubit experiments and then extend its application to the variational optimization of Hamiltonians for quantum chemistry and magnetism. We effectively demonstrate that the suppression of incoherent errors helps unearth otherwise inaccessible accuracies to the variational solutions using our noisy processor. These results demonstrate that error mitigation techniques will be critical to significantly enhance the capabilities of near-term quantum computing hardware.
  • PDF
    We provide a general method for efficiently simulating time-dependent Hamiltonian dynamics on a circuit-model based quantum computer. Our approach is based on approximating the truncated Dyson series of the evolution operator, extending the earlier proposal by Berry to evolution generated by explicitly time-dependent Hamiltonians. Two alternative strategies are proposed to implement time ordering while exploiting the superposition principle for sampling the Hamiltonian at different times. The resource cost of our simulation algorithm retains the optimal logarithmic dependence on the inverse of the desired precision.
  • PDF
    Gao's quantum union bound is a generalization of the union bound from probability theory and finds a range of applications in quantum communication theory, quantum algorithms, and quantum complexity theory [Phys. Rev. A, 92(5):052331, 2015]. It is relevant when performing a sequence of binary-outcome quantum measurements on a quantum state, giving the same bound that the classical union bound would, except with a scaling factor of four. In this paper, we improve upon Gao's quantum union bound, by proving a quantum union bound that involves a tunable parameter that can be optimized. This tunable parameter plays a similar role to a parameter involved in the Hayashi-Nagaoka inequality [IEEE Trans. Inf. Theory, 49(7):1753 (2003)], used often in quantum information theory when analyzing the error probability of a square-root measurement. An advantage of the proof delivered here is that it is elementary, relying only on basic properties of projectors, the Pythagorean theorem, and the Cauchy--Schwarz inequality. As a non-trivial application of our quantum union bound, we prove that a sequential decoding strategy for classical communication over a quantum channel achieves a lower bound on the channel's second-order coding rate. This demonstrates the advantage of our quantum union bound in the non-asymptotic regime, in which a communication channel is called a finite number of times.
  • PDF
    Graph states are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing. Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC+LPM+CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. We first show that deciding whether a graph state |G> can be transformed into another graph state |G'> using LC+LPM+CC is NP-Complete, even if |G'> is restricted to be the GHZ-state. However, we also provide efficient algorithms for two situations of practical interest: 1. |G> has Schmidt-rank width one and |G'> is a GHZ-state. The Schmidt-rank width is an entanglement measure of quantum states, meaning this algorithm is efficient if the original state has little entanglement. Our algorithm has runtime O(|V(G')||V(G)|^3), and is also efficient in practice even on small instances as further showcased by a freely available software implementation. 2. |G> is in a certain class of states with unbounded Schmidt-rank width, and |G'> is a GHZ-state of a constant size. Here the runtime is O(poly(|V(G)|)), showing that more efficient algorithms can in principle be found even for states holding a large amount of entanglement, as long as the output state has constant size. Our results make use of the insight that deciding whether a graph state |G> can be transformed to another graph state |G'> is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G' is a vertex-minor of a graph G. Many of the technical tools developed to obtain our results may be of independent interest.
  • PDF
    Quantum machine learning is expected to be one of the first potential general-purpose applications of near-term quantum devices. A major recent breakthrough in classical machine learning is the notion of generative adversarial training, where the gradients of a discriminator model are used to train a separate generative model. In this work and a companion paper, we extend adversarial training to the quantum domain and show how to construct generative adversarial networks using quantum circuits. Furthermore, we also show how to compute gradients -- a key element in generative adversarial network training -- using another quantum circuit. We give an example of a simple practical circuit ansatz to parametrize quantum machine learning models and perform a simple numerical experiment to demonstrate that quantum generative adversarial networks can be trained successfully.
  • PDF
    We study Projected Entangled Pair States (PEPS) with continuous virtual symmetries, i.e., symmetries in the virtual degrees of freedom, through an elementary class of models with SU(2) symmetry. Discrete symmetries of that kind have previously allowed for a comprehensive explanation of topological order in the PEPS formalism. We construct local parent Hamiltonians whose ground space with open boundaries is exactly parametrized by the PEPS wavefunction, and show how the ground state can be made unique by a suitable choice of boundary conditions. We also find that these models exhibit a logarithmic correction to the entanglement entropy and an extensive ground space degeneracy on systems with periodic boundaries, which suggests that they do not describe conventional gapped topological phases, but either critical models or some other exotic phase.
  • PDF
    A fundamental pursuit in complexity theory concerns reducing worst-case problems to average-case problems. There exist complexity classes such as PSPACE that admit worst-case to average-case reductions. Many other classes such as NP, however, the evidence so far is typically negative, in the sense that the existence of such reductions would cause collapses of the polynomial hierarchy. Basing cryptography, e.g., the average-case hardness of inverting one-way permutations, on NP-completeness is a particularly intriguing instance. We initiate a study of the quantum analogues of these questions and show that if NP-complete problems reduce to inverting one-way permutations using certain types of quantum reductions, then coNP $\subseteq$ QIP(2).
  • PDF
    We introduce a framework for the formal specification and verification of quantum circuits based on the Feynman path integral. Our formalism, built around exponential sums of polynomial functions, provides a structured and natural way of specifying quantum operations, particularly for quantum implementations of classical functions. Verification of circuits over all levels of the Clifford hierarchy with respect to either a specification or reference circuit is enabled by a novel rewrite system for exponential sums with free variables. Our algorithm is further shown to give a polynomial-time decision procedure for checking the equivalence of Clifford group circuits. We evaluate our methods by performing automated verification of optimized Clifford+T circuits with up to 100 qubits and thousands of T gates, as well as the functional verification of quantum algorithms using hundreds of qubits. Our experiments culminate in the automated verification of the Hidden Shift algorithm for a class of Boolean functions in a fraction of the time it has taken recent algorithms to simulate.
  • PDF
    The existence of a positive log-Sobolev constant implies a bound on the mixing time of a quantum dissipative evolution under the Markov approximation. For classical spin systems, such constant was proven to exist, under the assumption of a mixing condition in the Gibbs measure associated to their dynamics, via a quasi-factorization of the entropy in terms of the conditional entropy in some sub-$\sigma$-algebras. In this work we analyze analogous quasi-factorization results in the quantum case. For that, we define the quantum conditional relative entropy and prove several quasi-factorization results for it. As an illustration of their potential, we use one of them to obtain a positive log-Sobolev constant for the heat-bath dynamics with product fixed point.
  • PDF
    Mapping functions on bits to Hamiltonians acting on qubits has many applications in quantum computing. In particular, Hamiltonians representing Boolean functions are required for applications of quantum annealing or the quantum approximate optimization algorithm to combinatorial optimization problems. We show how such functions are naturally represented by Hamiltonians given as sums of Pauli $Z$ operators (Ising spin operators) with the terms of the sum corresponding to the function's Fourier expansion. For many classes of functions which are given by a compact description, such as a Boolean formula in conjunctive normal form that gives an instance of the satisfiability problem, it is #P-hard to compute its Hamiltonian representation. On the other hand, no such difficulty exists generally for constructing Hamiltonians representing a real function such as a sum of local Boolean clauses. We give composition rules for explicitly constructing Hamiltonians representing a wide variety of Boolean and real functions by combining Hamiltonians representing simpler clauses as building blocks. We apply our results to the construction of controlled-unitary operators, and to the special case of operators that compute function values in an ancilla qubit register. Finally, we outline several additional applications and extensions of our results. A primary goal of this paper is to provide a $\textit{design toolkit for quantum optimization}$ which may be utilized by experts and practitioners alike in the construction and analysis of new quantum algorithms, and at the same time to demystify the various constructions appearing in the literature.
  • PDF
    We introduce a new graphical framework for designing quantum error correction codes based on classical principles. A key feature of this graphical language, over previous approaches, is that it is closely related to that of factor graphs or graphical models in classical information theory and machine learning. It enables us to formulate the description of recently-introduced `coherent parity check' quantum error correction codes entirely within the language of classical information theory. This makes our construction accessible without requiring background in quantum error correction or even quantum mechanics in general. More importantly, this allows for a collaborative interplay where one can design new quantum error correction codes derived from classical codes.
  • PDF
    We investigate the problem of bounding the quantum process fidelity given bounds on the fidelities between target states and the action of a process on a set of pure input states. We formulate the problem as a semidefinite program and prove convexity of the minimum process fidelity as a function of the errors on the output states. We characterize the conditions required to uniquely determine a process in the case of no errors, and derive a lower bound on its fidelity in the limit of small errors for any set of input states satisfying these conditions. We then consider sets of input states whose one-dimensional projectors form a symmetric positive operator-valued measure (POVM). We prove that for such sets the minimum fidelity is bounded by a linear function of the average output state error. The minimal non-orthogonal symmetric POVM contains $d+1$ states, where $d$ is the Hilbert space dimension. Our bounds applied to these states provide an efficient method for estimating the process fidelity without the use of full process tomography.
  • PDF
    A logical proof of the Kochen-Specker theorem is one that relies only on the compatibility relations amongst a set of projectors (called a KS set) rather than their statistics relative to some fixed preparation. These compatibility relations can be abstractly represented by a contextuality scenario. We introduce a framework for obtaining noise-robust noncontextuality inequalities from contextuality scenarios that we will call KS-uncolourable scenarios. These include all those that appear in logical proofs of the KS theorem. Our approach here goes beyond the result of R. Kunjwal and R. W. Spekkens, Phys. Rev. Lett. 115, 110403 (2015), which relied on an explicit numerical enumeration of all the vertices of the polytope of (measurement) noncontextual assignments of probabilities to such a KS-uncolourable contextuality scenario. In particular, this work forms a necessary counterpart to the framework for noise-robust noncontextuality inequalities presented in R. Kunjwal, arXiv:1709.01098 [quant-ph] (2017), which only applies to KS-colourable contextuality scenarios. The framework we present here relies on a single hypergraph invariant, defined in R. Kunjwal, arXiv:1709.01098 [quant-ph] (2017), that is relevant for noise-robust noncontextuality inequalities arising from any KS-uncolourable contextuality scenario, namely, the weighted max-predictability. Indeed, the present work can also be viewed as a study of this hypergraph invariant. Significantly, none of the graph invariants arising in the graph-theoretic framework for KS contextuality due to Cabello, Severini, and Winter (Phys. Rev. Lett. 112, 040401 (2014)) are relevant for our noise-robust noncontextuality inequalities. In this sense, the framework we present for generalized contextuality applied to KS-uncolourable scenarios has no analogue in previous literature on KS-contextuality.
  • PDF
    In analogy with the classical complexity class Total Functional NP (TFNP), we introduce the complexity class of Total Functional QMA (TFQMA). In this complexity class one is given a family of quantum circuits $Q_n$ that take as input a classical string $x$ of length $n$ and a quantum state $\vert \psi \rangle$ on poly$(n)$ qubits, for some polynomial poly$(n)$, such that for all $x$ there exists at least one witness, i.e. a state $\vert \psi \rangle$ such that $Q_n(x, \vert \psi \rangle)=1$ with probability $\geq 2/3$. The functional problem is then, given $Q_n$ and $x$, find a $\vert \psi \rangle$ such that $Q_n(x, \vert \psi \rangle)=1$ with probability $\geq 2/3$. The complexity of this class lies between the functional analogs of BQP and QMA, denoted FBQP and FQMA respectively. We show that TFQMA can equivalently be defined as the functional analog of QMA$\cap$coQMA. We provide examples of problems that lie in TFQMA, coming from areas such as the complexity of k-local Hamiltonians and public key quantum money. In the context of black-box groups, we note that Group Non-Membership, which was known to belong to QMA, in fact belongs to TFQMA. We also provide an oracle with respect to which we have a separation between FBQP and TFQMA. In the conclusion we discuss the relation between TFQMA, public key quantum money, and the complexity of quantum states.
  • PDF
    Eigenvalues of 1-particle reduced density matrices of $N$-fermion states are upper bounded by $1/N$, resulting in a lower bound on entanglement entropy. We generalize these bounds to all other subspaces defined by Young diagrams in the Schur-Weyl decomposition of $\otimes^N\mathbb{C}^d$.
  • PDF
    Quantum communication between distant parties is based on suitable instances of shared entanglement. For efficiency reasons, in an anticipated quantum network beyond point-to-point communication, it is preferable that many parties can communicate simultaneously over the underlying infrastructure; however, bottlenecks in the network may cause delays. Sharing of multi-partite entangled states between parties offers a solution, allowing for parallel quantum communication. Specifically for the two-pair problem, the butterfly network provides the first instance of such an advantage in a bottleneck scenario. The underlying method differs from standard repeater network approaches in that it uses a graph state instead of maximally entangled pairs to achieve long-distance simultaneous communication. We will demonstrate how graph theoretic tools, and specifically local complementation, help decrease the number of required measurements compared to usual methods applied in repeater schemes. We will examine other examples of network architectures, where deploying local complementation techniques provides an advantage. We will finally consider the problem of extracting graph states for quantum communication via local Clifford operations and Pauli measurements, and discuss that while the hardness of the general problem is not known, interestingly, for specific classes of structured resources, polynomial time algorithms can be identified.
  • PDF
    A Bell test, which challenges the philosophical worldview of local realism against experimental observations, is a randomized trial requiring spatially-distributed entanglement, fast and high-efficiency detection, and unpredictable measurement settings. While technology can perfect the first two of these, and while technological randomness sources enable device-independent protocols based on Bell inequality violation, challenging local realism using physical randomizers inevitably makes assumptions about the same physics one aims to test. Bell himself noted this weakness of physical setting choices and argued that human free will could rigorously be used to assure unpredictability in Bell tests. Here we report a suite of local realism tests using human choices, avoiding assumptions about predictability in physics. We recruited ~100,000 human participants to play an online video game that incentivizes fast, sustained input of unpredictable bits while also illustrating Bell test methodology. The participants generated 97,347,490 binary choices, which were directed via a scalable web platform to twelve laboratories on five continents, in which 13 experiments tested local realism using photons, single atoms, atomic ensembles, and superconducting devices. Over a 12-hour period on the 30 Nov. 2016, participants worldwide provided a sustained flow of over 1000 bits/s to the experiments, which used different human-generated bits to choose each measurement setting. The observed correlations strongly contradict local realism and other realist positions in bi-partite and tri-partite scenarios. Project outcomes include closing of the freedom-of-choice loophole, gamification of statistical and quantum non-locality concepts, new methods for quantum-secured communications, a very large dataset of human-generated randomness, and networking techniques for global participation in experimental science.
  • PDF
    In this paper we consider what can be computed by a user interacting with a potentially malicious server, when the server performs polynomial-time quantum computation but the user can only perform polynomial-time classical (i.e., non-quantum) computation. Understanding the computational power of this model, which corresponds to polynomial-time quantum computation that can be efficiently verified classically, is a well-known open problem in quantum computing. Our result shows that computing the order of a solvable group, which is one of the most general problems for which quantum computing exhibits an exponential speed-up with respect to classical computing, can be realized in this model.
  • PDF
    We study the sampling complexity of a probability distribution associated with an ensemble of identical non-interacting bosons undergoing quantum random walk on a one-dimensional lattice. With uniform nearest-neighboring hopping and for times logarithmic in the size of the system, one can efficiently sample the distribution. For longer times, we know of no efficient sampling algorithm. With time-dependent hopping and optimal control, we design the time evolution to approximate an arbitrary Haar-random unitary map analogous to that designed for photons in a linear optical network to yield quantum supremacy. We illustrate an experimental realization in a spinor optical lattice of ultracold atoms.
  • PDF
    We study classical query algorithms with post-selection, and find that they are closely connected to rational functions with nonnegative coefficients. We show that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations (with nonnegative coefficients) to the Majority function. This lower bound can be generalised to arbitrary symmetric functions, and allows us to find an unbounded separation between non-deterministic quantum and post-selected classical query complexity. All lower bounds carry over into the communication complexity setting. We show that the zero-error variants of post-selected query algorithms are equivalent to non-deterministic classical query algorithms, which in turn are characterised by nonnegative polynomials, and for some problems require exponentially more queries to the input than their bounded-error counterparts. Finally, we describe a post-selected query algorithm for approximating the Majority function, and an efficient query algorithm for approximate counting.
  • PDF
    Tree tensor network descriptions of critical quantum spin chains are empirically known to reproduce correlation functions matching CFT predictions in the continuum limit. It is natural to seek a more complete correspondence, additionally incorporating dynamics. On the CFT side, this is determined by a representation of the diffeomorphism group of the circle. In a remarkable series of papers, Jones outlined a research program where the Thompson group T takes the role of the latter in the discrete setting, and representations of T are constructed from certain elements of a subfactor planar algebra. He also showed that for a particular example of such a construction, this approach only yields - in the continuum limit - a representation which is highly discontinuous and hence unphysical. Here we show that the same issue arises generically when considering tree tensor networks: the set of coarse-graining maps yielding discontinuous representations has full measure in the set of all isometries. This extends Jones' no-go example to typical elements of the so-called tensor planar algebra. We also identify an easily verified necessary condition for a continuous limit to exist. This singles out a particular class of tree tensor networks. Our considerations apply to recent approaches for introducing dynamics in holographic codes.
  • PDF
    We develop circuit implementations for digital-level quantum Hamiltonian dynamics simulation algorithms suitable for implementation on a reconfigurable quantum computer, such as the trapped ions. Our focus is on the co-design of a problem, its solution, and quantum hardware capable of executing the solution at the minimal cost expressed in terms of the quantum computing resources used, while demonstrating the solution of an instance of a scientifically interesting problem that is intractable classically. The choice for Hamiltonian dynamics simulation is due to the combination of its usefulness in the study of equilibrium in closed quantum mechanical systems, a low cost in the implementation by quantum algorithms, and the difficulty of classical simulation. By targeting a specific type of quantum computer and tailoring the problem instance and solution to suit physical constraints imposed by the hardware, we are able to reduce the resource counts by a factor of 10 in a physical-level implementation and a factor of 15 in a fault-tolerant implementation over state of the art.
  • PDF
    Span programs characterize the quantum query complexity of \emphbinary functions $f:\{0,1\}^n \to \{0,1\}$ up to a constant factor. In this paper we generalize the notion of span programs for functions with \emphnon-binary input and/or output alphabets $f:[\ell]^n \to [m]$. We show that for any non-binary span program for such a function $f$ with complexity $C$, the quantum query complexity of $f$ is at most $Q(f)=O(C)$. Conversely, there exists a non-binary span program for $f$ with complexity $\sqrt{\ell-1}\,Q(f)$. Thus, we conclude that non-binary span programs characterize the quantum query complexity of $f$ up to a factor of order at most $\sqrt{\ell-1}$. By giving explicit examples, we show that this $\sqrt{\ell-1}$ factor cannot be improved. We also generalize the notion of span programs for a special class of relations and prove similar results. Learning graphs provide another tool for designing quantum query algorithms for binary functions. In this paper, we also generalize this tool for non-binary functions.
  • PDF
    Implementing quantum algorithms is essential for quantum computation. We study the implementation of three quantum algorithms by performing homodyne measurements on a two-dimensional temporal continuous-variable cluster state. We first review the generation of temporal cluster states and the implementation of gates using the measurement-based model. Alongside this we discuss methods to introduce non-Gaussianity into the cluster states. The first algorithm we consider is Gaussian Boson Sampling in which only Gaussian unitaries need to be implemented. Taking into account the fact that input states are also Gaussian, the errors due to the effect of finite squeezing can be corrected, provided a moderate amount of online squeezing is available. This helps to construct a large Gaussian Boson Sampling machine. The second algorithm is the continuous-variable Instantaneous Quantum Polynomial circuit in which one needs to implement non-Gaussian gates, such as the cubic phase gate. We discuss several methods of implementing the cubic phase gate and fit them into the temporal cluster state architecture. The third algorithm is the continuous-variable version of Grover's search algorithm, the main challenge of which is the implementation of the inversion operator. We propose a method to implement the inversion operator by injecting a resource state into a teleportation circuit. The resource state is simulated using the Strawberry Fields quantum software package.
  • PDF
    The emergence of statistical mechanics for isolated classical systems comes about through chaotic dynamics and ergodicity. Here we review how similar questions can be answered in quantum systems. The crucial point is that individual energy eigenstates behave in many ways like a statistical ensemble. A more detailed statement of this is named the Eigenstate Thermalization Hypothesis (ETH). The reasons for why it works in so many cases are rooted in the early work of Wigner on random matrix theory and our understanding of quantum chaos. The ETH has now been studied extensively by both analytic and numerical means, and applied to a number of physical situations ranging from black hole physics to condensed matter systems. It has recently become the focus of a number of experiments in highly isolated systems. Current theoretical work also focuses on where the ETH breaks down leading to new interesting phenomena. This review of the ETH takes a somewhat intuitive approach as to why it works and how this informs our understanding of many body quantum states.
  • PDF
    We study the performance of quantum error correction (QEC) on a system undergoing open-system (OS) dynamics. The noise on the system originates from a joint quantum channel on the system-bath composite, a framework that includes and interpolates between the commonly used system-only quantum noise channel model and the system-bath Hamiltonian noise model. We derive the perfect OSQEC conditions, with QEC recovery only on the system and not the inaccessible bath. When the noise is only approximately correctable, the generic case of interest, we quantify the performance of OSQEC using worst-case fidelity. We find that the leading deviation from unit fidelity after recovery is quadratic in the uncorrectable part, a result reminiscent of past work on approximate QEC for system-only noise, although the approach here requires the use of different techniques than in past work.
  • PDF
    We study novel invariants of modular categories that are beyond the modular data, with an eye towards a simple set of complete invariants for modular categories. Our focus is on the $W$-matrix $-$the quantum invariant of a colored framed Whitehead link from the associated TQFT of a modular category. We prove that the $W$-matrix and the set of punctured $S$-matrices are strictly beyond the modular data $(S,T)$. Whether or not the triple $(S,T,W)$ constitutes a complete invariant of modular categories remains an open question.
  • PDF
    Werner states have a host of interesting properties, which often serve to illuminate the unusual properties of quantum information. Starting from these states, one may define a family of quantum channels, known as the Holevo-Werner channels, which themselves afford several unusual properties. In this paper we use the teleportation covariance of these channels to upper bound their two-way assisted quantum and secret-key capacities. This bound may be expressed in terms of relative entropy distances, such as the relative entropy of entanglement, and also in terms of the squashed entanglement. Most interestingly, we show that the relative entropy bounds are strictly sub-additive for a sub-class of the Holevo-Werner channels, so that their regularisation provides a tighter performance. These information-theoretic results are first found for point-to-point communication and then extended to repeater chains and quantum networks, under different types of routing strategies.
  • PDF
    Symmetry-Protected Topological (SPT) phases are short-range entangled (SRE) gapped phases of quantum matter protected by global symmetries, that cannot be unitarily and adiabatically deformed to a trivial phase without closing the gap or breaking symmetry. In this work, we show that, for several SPT phases, enlarging symmetries may effectively achieve the consequences of explicitly breaking symmetries. In other words, we demonstrate that non-trivial SPT phases can be unwound to trivial ones by \emphsymmetry extension --- through a path where the Hilbert space is \emphenlarged and the Hamiltonian is invariant under an \emphextended symmetry group applying the idea of Wang-Wen-Witten [arXiv:1705.06728]. We show examples of both bosonic and fermionic SPT phases in 1+1 dimensions, including a Haldane spin chain and layers of Kitaev's Majorana fermionic chains. By adding degrees of freedom into the boundary/bulk, we can lift the zero mode degeneracy, or unwind the whole system. Furthermore, based on properties of Schur cover, we sketch a general picture of unwinding applicable to any 1+1D bosonic SPT phase protected by onsite finite symmetry. Altogether we show that SRE states can be unwound by \emphsymmetry breaking, \emphinversion and \emphsymmetry extension.
  • PDF
    We study the problem of transmission of classical messages through a quantum channel in several network scenarios in the one-shot setting. We consider both the entanglement assisted and unassisted cases for the point to point quantum channel, quantum multiple-access channel, quantum channel with state and the quantum broadcast channel. We show that it is possible to near-optimally characterize the amount of communication that can be transmitted in these scenarios, using the position-based decoding strategy introduced in a prior work [Anshu, Jain and Warsi, 2017]. In the process, we provide a short and elementary proof of the converse for entanglement-assisted quantum channel coding in terms of the quantum hypothesis testing divergence (obtained earlier in [Matthews and Wehner, 2014]). Our proof has the additional utility that it naturally extends to various network scenarios mentioned above. Furthermore, none of our achievability results require a simultaneous decoding strategy, existence of which is an important open question in quantum Shannon theory.
  • PDF
    We propose an encoding for topological quantum computing with mapping class group representations, which is obviously not universal without leakage. We are interested in whether or not some generalized version of the Knill-Gottesmann theorem holds for such a quantum computing scheme, and how to make universal gate sets with supplemental primitives. As a first step, we prove that for abelian anyons, all gates from mapping class group representations are generalized Clifford gates, and this theorem does not hold for the Fibonacci anyon.
  • PDF
    We introduce and study the entanglement breaking rank of an entanglement breaking channel. We show that the problem of computing the entanglement breaking rank of the channel \beginalign* \mathfrak Z(X) = \frac1d+1(X+\textTr(X)\mathbb I_d) \endalign* is equivalent to the existence problem of symmetric informationally-complete POVMs.
  • PDF
    In this work we investigate methods to improve the efficiency and scalability of quantum algorithms for quantum chemistry applications. We propose a transformation of the electronic structure Hamiltonian in the second quantization framework into the particle-hole (p/h) picture, which offers a better starting point for the expansion of the trial wavefunction. The state of the molecular system at study is parametrized in a way to efficiently explore the sector of the molecular Fock space that contains the desired solution. To this end, we explore several trial wavefunctions to identify the most efficient parameterization of the molecular ground state. Taking advantage of known post-Hartree Fock quantum chemistry approaches and heuristic Hilbert space search quantum algorithms, we propose a new family of quantum circuits based on exchange-type gates that enable accurate calculations while keeping the gate count (i.e., the circuit depth) low. The particle-hole implementation of the Unitary Coupled Cluster (UCC) method within the Variational Quantum Eigensolver approach gives rise to an efficient quantum algorithm, named q-UCC , with important advantages compared to the straightforward 'translation' of the classical Coupled Cluster counterpart. In particular, we show how a single Trotter step can accurately and efficiently reproduce the ground state energies of simple molecular systems.

Recent comments

Max Lu Apr 25 2018 22:08 UTC

"This is a very inspiring paper! The new framework (ZR = All Reality) it provided allows us to understand all kinds of different reality technologies (VR, AR, MR, XR etc) that are currently loosely connected to each other and has been confusing to many people. Instead of treating our perceived sens

...(continued)
Stefano Pirandola Apr 23 2018 12:23 UTC

The most important reading here is Sam Braunstein's foundational paper: https://authors.library.caltech.edu/3827/1/BRAprl98.pdf published in January 98, already containing the key results for the strong convergence of the CV protocol. This is a must-read for those interested in CV quantum informatio

...(continued)
Mark M. Wilde Apr 23 2018 12:09 UTC

One should also consult my paper "Strong and uniform convergence in the teleportation simulation of bosonic Gaussian channels" https://arxiv.org/abs/1712.00145v4 posted in January 2018, in this context.

Stefano Pirandola Apr 23 2018 11:46 UTC

Some quick clarifications on the Braunstein-Kimble (BK) protocol for CV teleportation
and the associated teleportation simulation of bosonic channels.
(Disclaimer: the following is rather technical and CVs might not be so popular on this blog...so I guess this post will get a lot of dislikes :)

1)

...(continued)
NJBouman Apr 22 2018 18:26 UTC

[Fredrik Johansson][1] has pointed out to me (the author) the following about the multiplication benchmark w.r.t. GMP. This will be taken into account in the upcoming revision.

Fredrik Johansson wrote:
> You shouldn't be comparing your code to `mpn_mul`, because this function is not actually th

...(continued)
Joel Wallman Apr 18 2018 13:34 UTC

A very nice approach! Could you clarify the conclusion a little bit though? The aspirational goal for a quantum benchmark is to test how well we approximate a *specific* representation of a group (up to similarity transforms), whereas what your approach demonstrates is that without additional knowle

...(continued)
serfati philippe Mar 29 2018 14:07 UTC

see my 2 papers on direction of vorticity (nov1996 + feb1999) = https://www.researchgate.net/profile/Philippe_Serfati (published author, see also mendeley, academia.edu, orcid etc)

serfati philippe Mar 29 2018 13:34 UTC

see my 4 papers, 1998-1999, on contact and superposed vortex patches, cusps (and eg splashs), corners, generalized ones on lR^n and (ir/)regular ones =. http://www.researchgate.net/profile/Philippe_Serfati/ (published author).

Luis Cruz Mar 16 2018 15:34 UTC

Related Work:

- [Performance-Based Guidelines for Energy Efficient Mobile Applications](http://ieeexplore.ieee.org/document/7972717/)
- [Leafactor: Improving Energy Efficiency of Android Apps via Automatic Refactoring](http://ieeexplore.ieee.org/document/7972807/)

Dan Elton Mar 16 2018 04:36 UTC

Comments are appreciated. Message me here or on twitter @moreisdifferent

Code is open source and available at :
[https://github.com/delton137/PIMD-F90][1]

[1]: https://github.com/delton137/PIMD-F90