Search

Quantum computing is one of the most enticing computational paradigms with the potential to revolutionize diverse areas of future-generation computational systems. While quantum computing hardware has advanced rapidly, from tiny laboratory experiments to quantum chips that can outperform even the largest supercomputers on specialized computational tasks, these noisy-intermediate scale quantum (NISQ) processors are still too small and non-robust to be directly useful for any real-world applications. In this paper, we describe NASA's work in assessing and advancing the potential of quantum computing. We discuss advances in algorithms, both near- and longer-term, and the results of our explorations on current hardware as well as with simulations, including illustrating the benefits of algorithm-hardware co-design in the NISQ era. This work also includes physics-inspired classical algorithms that can be used at application scale today. We discuss innovative tools supporting the assessment and advancement of quantum computing and describe improved methods for simulating quantum systems of various types on high-performance computing systems that incorporate realistic error models. We provide an overview of recent methods for benchmarking, evaluating, and characterizing quantum hardware for error mitigation, as well as insights into fundamental quantum physics that can be harnessed for computational purposes., Comment: 27 pages, 0 figures

We introduce state-of-the-art protocols to distill indistinguishable photons, reducing distinguishability error rates by a factor of $n$, while using a modest amount of resources scaling only linearly in $n$. Our resource requirements are both significantly lower and have fewer hardware requirements than previous works, making large-scale distillation experimentally feasible for the first time. This efficient reduction of distinguishability error rates has direct applications to fault-tolerant linear optical quantum computation, potentially leading to improved thresholds for photon loss errors and allowing smaller code distances, thus reducing overall resource costs. Our protocols are based on Fourier transforms on finite abelian groups, special cases of which include the discrete Fourier transform and Hadamard matrices. This general perspective allows us to unify previous results on distillation protocols and introduce a large family of efficient schemes. We utilize the rich mathematical structure of Fourier transforms, including symmetries and related suppression laws, to quantify the performance of these distillation protocols both analytically and numerically. Finally, our work resolves an open question concerning suppression laws for the $n$-photon discrete Fourier transform: the suppression laws are exactly characterized by the well-known Zero Transmission Law if and only if $n$ is a prime power., Comment: V2: Updated Th. III.9 with stronger statement, correcting mistake in V1 proof. Include discussion and analysis of more general Fourier protocols over abelian groups. Other minor changes. V3: Updated exposition, added appendix discussing relevance to fault-tolerant linear optical quantum computation, and fixed a typo in Theorem III.16

We investigate distributed classical and quantum approaches for the survivable network design problem (SNDP), sometimes called the generalized Steiner problem. These problems generalize many complex graph problems of interest, such as the traveling salesperson problem, the Steiner tree problem, and the k-connected network problem. To our knowledge, no classical or quantum algorithms for the SNDP have been formulated in the distributed settings we consider. We describe algorithms that are heuristics for the general problem but give concrete approximation bounds under specific parameterizations of the SNDP, which in particular hold for the three aforementioned problems that SNDP generalizes. We use a classical, centralized algorithmic framework first studied in (Goemans & Bertsimas 1993) and provide a distributed implementation thereof. Notably, we obtain asymptotic quantum speedups by leveraging quantum shortest path computations in this framework, generalizing recent work of (Kerger et al. 2023). These results raise the question of whether there is a separation between the classical and quantum models for application-scale instances of the problems considered., Comment: 12 pages, 0 figures

Theoretically understanding and experimentally characterizing and modifying the underlying Hamiltonian of a quantum system is of utmost importance in achieving high-fidelity quantum gates for quantum computing. In this work, we explore the use of dynamical decoupling (DD) in characterizing undesired two-qubit couplings as well as the underlying single-qubit decoherence, and in suppressing them. We develop a syncopated dynamical decoupling technique which protects against decoherence and selectively targets unwanted two-qubit interactions, overcoming both significant hurdles to achieving precise quantum control and realizing quantum computing on many hardware prototypes. On a transmon-qubit-based superconducting quantum device, we identify separate white and $1/f$ noise components underlying the single-qubit decoherence and a static ZZ coupling between pairs of qubits. We suppress these errors using syncopated dynamical decoupling in two-qubit benchmarking experiments and significantly boost performance in a realistic algorithmic quantum circuit.

Quantum networking at many scales will be critical to future quantum technologies and experiments on quantum systems. Photonic links enable quantum networking. They will connect co-located quantum processors to enable large-scale quantum computers, provide links between distant quantum computers to support distributed, delegated, and blind quantum computing, and will link distant nodes in space enabling new tests of fundamental physics. Here, we discuss recent work advancing photonic tools and protocols that support quantum networking. We provide analytical results and numerics for the effect of distinguishability errors on key photonic circuits; we considered a variety of error models and developed new metrics for benchmarking the quality of generated photonic states. We review a distillation protocol by one of the authors that mitigates distinguishability errors. We also review recent results by a subset of the authors on the efficient simulation of photonic circuits via approximation by coherent states. We study some interactions between the theory of universal sets, unitary t-designs, and photonics: while many of the results we state in this direction may be known to experts, we aim to bring them to the attention of the broader quantum information science community and to phrase them in ways that are more familiar to this community. We prove, translating a result from representation theory, that there are no non-universal infinite closed $2$-designs in $U(V)$ when $\dim V \geq 2$. As a consequence, we observe that linear optical unitaries form a $1$-design but not a 2-design. Finally, we apply a result of Oszmaniec and Zimbor\'{a}s to prove that augmenting the linear optical unitaries with any nontrivial SNAP gate is sufficient to achieve universality., Comment: Submitted to SPIE Photonics West 2024, comments welcome

We discuss guidelines for evaluating the performance of parameterized stochastic solvers for optimization problems, with particular attention to systems that employ novel hardware, such as digital quantum processors running variational algorithms, analog processors performing quantum annealing, or coherent Ising Machines. We illustrate through an example a benchmarking procedure grounded in the statistical analysis of the expectation of a given performance metric measured in a test environment. In particular, we discuss the necessity and cost of setting parameters that affect the algorithm's performance. The optimal value of these parameters could vary significantly between instances of the same target problem. We present an open-source software package that facilitates the design, evaluation, and visualization of practical parameter tuning strategies for complex use of the heterogeneous components of the solver. We examine in detail an example using parallel tempering and a simulator of a photonic Coherent Ising Machine computing and display the scoring of an illustrative baseline family of parameter-setting strategies that feature an exploration-exploitation trade-off., Comment: 13 pages, 6 figures

In this paper we present a novel method to generate hard instances with planted solutions based on the public-private McEliece post-quantum cryptographic protocol. Unlike other planting methods rooted in the infinite-size statistical analysis, our cryptographic protocol generates instances which are all hard (in cryptographic terms), with the hardness tuned by the size of the private key, and with a guaranteed unique ground state. More importantly, because of the private-public key protocol, planted solutions cannot be easily recovered by a direct inspection of the planted instances without the knowledge of the private key used to generate them, therefore making our protocol suitable to test and evaluate quantum devices without the risk of "backdoors" being exploited.

We develop a hardware-efficient ansatz for variational optimization, derived from existing ansatze in the literature, that parametrizes subsets of all interactions in the Cost Hamiltonian in each layer. We treat gate orderings as a variational parameter and observe that doing so can provide significant performance boosts in experiments. We carried out experimental runs of a compilation-optimized implementation of fully-connected Sherrington-Kirkpatrick Hamiltonians on a 50-qubit linear-chain subsystem of Rigetti Aspen-M-3 transmon processor. Our results indicate that, for the best circuit designs tested, the average performance at optimized angles and gate orderings increases with circuit depth (using more parameters), despite the presence of a high level of noise. We report performance significantly better than using a random guess oracle for circuits involving up to approx 5000 two-qubit and approx 5000 one-qubit native gates. We additionally discuss various takeaways of our results toward more effective utilization of current and future quantum processors for optimization., Comment: v2: extended experimental results, updated references, fixed typos; v3: improved main narration, added new experimental data and analysis, updated references, fixed typos; v4: slightly improved narration, updated references 15+8 pages; 3+5 figures

The CONGEST and CONGEST-CLIQUE models have been carefully studied to represent situations where the communication bandwidth between processors in a network is severely limited. Messages of only $O(log(n))$ bits of information each may be sent between processors in each round. The quantum versions of these models allow the processors instead to communicate and compute with quantum bits under the same bandwidth limitations. This leads to the following natural research question: What problems can be solved more efficiently in these quantum models than in the classical ones? Building on existing work, we contribute to this question in two ways. Firstly, we present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which uses $\tilde{O}(n^{1/4})$ rounds of communication and $\tilde{O}(n^{9/4})$ messages, where $n$ is the number of nodes in the network. The algorithms thus achieve a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithmic frameworks with quantum subroutines. An existing framework for using distributed version of Grover's search algorithm to accelerate triangle finding lies at the core of the asymptotic speedup. Secondly, we carefully characterize the constants and logarithmic factors involved in our algorithms as well as related algorithms, otherwise commonly obscured by $\tilde{O}$ notation. The analysis shows that some improvements are needed to render both our and existing related quantum and classical algorithms practical, as their asymptotic speedups only help for very large values of $n$., Comment: 25 pages, 0 figures

Combinatorial optimization is a broadly attractive area for potential quantum advantage, but no quantum algorithm has yet made the leap. Noise in quantum hardware remains a challenge, and more sophisticated quantum-classical algorithms are required to bolster their performance. Here, we introduce an iterative quantum heuristic optimization algorithm to solve combinatorial optimization problems. The quantum algorithm reduces to a classical greedy algorithm in the presence of strong noise. We implement the quantum algorithm on a programmable superconducting quantum system using up to 72 qubits for solving paradigmatic Sherrington-Kirkpatrick Ising spin glass problems. We find the quantum algorithm systematically outperforms its classical greedy counterpart, signaling a quantum enhancement. Moreover, we observe an absolute performance comparable with a state-of-the-art semidefinite programming method. Classical simulations of the algorithm illustrate that a key challenge to reaching quantum advantage remains improving the quantum device characteristics., Comment: 9 pages, 5 figures (+ 12 pages, 11 figures)

A recent paper by two of us and co-workers, based on an extended Wigner's friend scenario, demonstrated that certain empirical correlations predicted by quantum theory (QT) violate inequalities derived from a set of metaphysical assumptions we called "Local Friendliness" (LF). These assumptions are strictly weaker than those used for deriving Bell inequalities. Crucial to the theorem was the premise that a quantum system with reversible evolution could be an observer (colloquially, a "friend"). However, that paper was noncommittal on what would constitute an observer for the purpose of an experiment. Here, we present a new LF no-go theorem which takes seriously the idea that a system's having *thoughts* is a sufficient condition for it to be an observer. Our new derivation of the LF inequalities uses four metaphysical assumptions, three of which are thought-related, including one that is explicitly called "Friendliness". These four assumptions, in conjunction, allow one to derive LF inequalities for experiments involving the type of system that "Friendliness" refers to. In addition to these four metaphysical assumptions, this new no-go theorem requires two assumptions about what is *technologically* feasible: Human-Level Artificial Intelligence, and Universal Quantum Computing which is fast and large scale. The latter is often motivated by the belief that QT is universal, but this is *not* an assumption of the theorem. The intent of the new theorem is to give a clear goal for future experimentalists, and a clear motivation for trying to achieve that goal. We review various approaches to QT in light of our theorem. The popular stance that "quantum theory needs no interpretation" does not question any of our assumptions and so is ruled out. Finally, we quantitatively discuss how difficult the experiment we envisage would be, and briefly discuss milestones on the paths towards it., Comment: 44 pages, 3 figures. Accepted for publication in uantum

Developing state-of-the-art classical simulators of quantum circuits is of utmost importance to test and evaluate early quantum technology and understand the true potential of full-blown error-corrected quantum computers. In the past few years, multiple theoretical and numerical advances have continuously pushed the boundary of what is classically simulable, hence the development of a plethora of tools which are often limited to a specific purpose or designed for a particular hardware (e.g. CPUs vs. GPUs). Moreover, such tools are typically developed using tailored languages and syntax, which makes it hard to compare results from, and create hybrid approaches using, different simulation techniques. To support unified and optimized use of these techniques across platforms, we developed HybridQ, a highly extensible platform designed to provide a common framework to integrate multiple state-of-the-art techniques to run on a variety of hardware. The philosophy behind its development has been driven by three main pillars: "Easy to Use", "Easy to Extend", and "Use the Best Available Technology". The powerful tools of HybridQ allow users to manipulate, develop, and extend noiseless and noisy circuits for different hardware architectures. HybridQ supports large-scale high-performance computing (HPC) simulations, automatically balancing workload among different processor nodes and enabling the use of multiple backends to maximize parallel efficiency. Everything is then glued together by a simple and expressive language that allows seamless switching from one technique to another as well as from one hardware to the next, without the need to write lengthy translations, thus greatly simplifying the development of new hybrid algorithms and techniques., Comment: https://github.com/nasa/hybridq

We develop a framework for analyzing layered quantum algorithms such as quantum alternating operator ans\"atze. Our framework relates quantum cost gradient operators, derived from the cost and mixing Hamiltonians, to classical cost difference functions that reflect cost function neighborhood structure. By considering QAOA circuits from the Heisenberg picture, we derive exact general expressions for expectation values as series expansions in the algorithm parameters, cost gradient operators, and cost difference functions. This enables novel interpretability and insight into QAOA behavior in various parameter regimes. For single-level QAOA1 we show the leading-order changes in the output probabilities and cost expectation value explicitly in terms of classical cost differences, for arbitrary cost functions. This demonstrates that, for sufficiently small positive parameters, probability flows from lower to higher cost states on average. By selecting signs of the parameters, we can control the direction of flow. We use these results to derive a classical random algorithm emulating QAOA1 in the small-parameter regime, i.e., that produces bitstring samples with the same probabilities as QAOA1 up to small error. For deeper QAOAp circuits we apply our framework to derive analogous and additional results in several settings. In particular we show QAOA always beats random guessing. We describe how our framework incorporates cost Hamiltonian locality for specific problem classes, including causal cone approaches, and applies to QAOA performance analysis with arbitrary parameters. We illuminate our results with a number of examples including applications to QUBO problems, MaxCut, and variants of MaxSat. We illustrate the application to QAOA circuits using mixing unitaries beyond the transverse-field mixer through two examples of constrained optimization, Max Independent Set and Graph Coloring., Comment: Updated to match published version

In order to assess whether quantum resources can provide an advantage over classical computation, it is necessary to characterize and benchmark the non-classical properties of quantum algorithms in a practical manner. In this paper, we show that using measurements in no more than 3 out of the possible $3^N$ bases, one can not only reconstruct the single-qubit reduced density matrices and measure the ability to create coherent superpositions, but also possibly verify entanglement across all $N$ qubits participating in the algorithm. We introduce a family of generalized Bell-type observables for which we establish an upper bound to the expectation values in fully separable states by proving a generalization of the Cauchy-Schwarz inequality, which may serve of independent interest. We demonstrate that a subset of such observables can serve as entanglement witnesses for QAOA-MaxCut states, and further argue that they are especially well tailored for this purpose by defining and computing an entanglement potency metric on witnesses. A subset of these observables also certify, in a weaker sense, the entanglement in GHZ states, which share the $\mathbb{Z}_2$ symmetry of QAOA-MaxCut. The construction of such witnesses follows directly from the cost Hamiltonian to be optimized, and not through the standard technique of using the projector of the state being certified. It may thus provide insights to construct similar witnesses for other variational algorithms prevalent in the NISQ era. We demonstrate our ideas with proof-of-concept experiments on the Rigetti Aspen-9 chip for ansatze containing up to 24 qubits.

Given quantum hardware that enables sampling from a family of natively implemented Hamiltonians, how well can one use that hardware to sample from a Hamiltonian outside that family? A common approach is to minor embed the desired Hamiltonian in a native Hamiltonian. In Phys. Rev. Research 2, 023020 (2020) it was shown that minor embedding can be detrimental for classical thermal sampling. Here, we generalize these results by considering quantum thermal sampling in the transverse-field Ising model, i.e. sampling a Hamiltonian with non-zero off diagonal terms. To study these systems numerically we introduce a modification to standard cluster update quantum Monte-Carlo (QMC) techniques, which allows us to much more efficiently obtain thermal samples of an embedded Hamiltonian, enabling us to simulate systems of much larger sizes and larger transverse-field strengths than would otherwise be possible. Our numerics focus on models that can be implemented on current quantum devices using planar two-dimensional lattices, which exhibit finite-temperature quantum phase transitions. Our results include: i) An estimate on the probability to sample the logical subspace directly as a function of transverse-field, temperature, and total system size, which agrees with QMC simulations. ii) We show that typically measured observables (diagonal energy and magnetization) are biased by the embedding process, in the regime of intermediate transverse field strength, meaning that the extracted values are not the same as in the native model. iii) By considering individual embedding realizations akin to 'realizations of disorder', we provide numerical evidence suggesting that as the embedding size is increased, the critical point shifts to increasingly large values of the transverse-field., Comment: 11+5 pages, 16 Figures. V2: updated to published version, including new results by averaging over embedding realizations

This is an updated version of supplementary information to accompany "Quantum supremacy using a programmable superconducting processor", an article published in the October 24, 2019 issue of Nature. The main article is freely available at https://www.nature.com/articles/s41586-019-1666-5. Summary of changes since arXiv:1910.11333v1 (submitted 23 Oct 2019): added URL for qFlex source code; added Erratum section; added Figure S41 comparing statistical and total uncertainty for log and linear XEB; new References [1,65]; miscellaneous updates for clarity and style consistency; miscellaneous typographical and formatting corrections., Comment: 67 pages, 51 figures

Advances in techniques for thermal sampling in classical and quantum systems would deepen understanding of the underlying physics. Unfortunately, one often has to rely solely on inexact numerical simulation, due to the intractability of computing the partition function in many systems of interest. Emerging hardware, such as quantum annealers, provide novel tools for such investigations, but it is well known that studying general, non-native systems on such devices requires graph minor embedding, at the expense of introducing additional variables. The effect of embedding for sampling is more pronounced than for optimization; for optimization one is just concerned with the ground state physics, whereas for sampling one needs to consider states at all energies. We argue that as the system size or the embedding size grows, the chance of a sample being in the subspace of interest - the logical subspace - can be exponentially suppressed. Though the severity of this scaling can be lessened through favorable parameter choices, certain physical constraints (such as a fixed temperature and range of couplings) provide hard limits on what is currently feasible. Furthermore, we show that up to some practical and reasonable assumptions, any type of post-processing to project samples back into the logical subspace will bias the resulting statistics. We introduce a new such technique, based on resampling, that substantially outperforms majority vote, which is shown to fail quite dramatically at preserving distribution properties., Comment: 14+1 pages, 13 Figures. v2: updated to published version, including additional discussions throughout

The practical use of many types of near-term quantum computers requires accounting for their limited connectivity. One way of overcoming limited connectivity is to insert swaps in the circuit so that logical operations can be performed on physically adjacent qubits, which we refer to as solving the `routing via matchings' problem. We address the routing problem for families of quantum circuits defined by a hypergraph wherein each hyperedge corresponds to a potential gate. Our main result is that any unordered set of $k$-qubit gates on distinct $k$-qubit subsets of $n$ logical qubits can be ordered and parallelized in $O(n^{k-1})$ depth using a linear arrangement of $n$ physical qubits; the construction is completely general and achieves optimal scaling in the case where gates acting on all $\binom{n}{k}$ sets of $k$ qubits are desired. We highlight two classes of problems for which our method is particularly useful. First, it applies to sets of mutually commuting gates, as in the (diagonal) phase separators of Quantum Alternating Operator Ansatz (Quantum Approximate Optimization Algorithm) circuits. For example, a single level of a QAOA circuit for Maximum Cut can be implemented in linear depth, and a single level for $3$-SAT in quadratic depth. Second, it applies to sets of gates that do not commute but for which compilation efficiency is the dominant criterion in their ordering. In particular, it can be adapted to Trotterized time-evolution of fermionic Hamiltonians under the Jordan-Wigner transformation, and also to non-standard mixers in QAOA. Using our method, a single Trotter step of the electronic structure Hamiltonian in an arbitrary basis of $n$ orbitals can be done in $O(n^3)$ depth while a Trotter step of the unitary coupled cluster singles and doubles method can be implemented in $O(n^2 \eta)$ depth, where $\eta$ is the number of electrons.

For the last few years, the NASA Quantum Artificial Intelligence Laboratory (QuAIL) has been performing research to assess the potential impact of quantum computers on challenging computational problems relevant to future NASA missions. A key aspect of this research is devising methods to most effectively utilize emerging quantum computing hardware. Research questions include what experiments on early quantum hardware would give the most insight into the potential impact of quantum computing, the design of algorithms to explore on such hardware, and the development of tools to minimize the quantum resource requirements. We survey work relevant to these questions, with a particular emphasis on our recent work in quantum algorithms and applications, in elucidating mechanisms of quantum mechanics and their uses for quantum computational purposes, and in simulation, compilation, and physics-inspired classical algorithms. To our early application thrusts in planning and scheduling, fault diagnosis, and machine learning, we add thrusts related to robustness of communication networks and the simulation of many-body systems for material science and chemistry. We provide a brief update on quantum annealing work, but concentrate on gate-model quantum computing research advances within the last couple of years., Comment: 20 pages plus extensive references, 3 figures

Noisy Intermediate-Scale Quantum (NISQ) computers are entering an era in which they can perform computational tasks beyond the capabilities of the most powerful classical computers, thereby achieving "Quantum Supremacy", a major milestone in quantum computing. NISQ Supremacy requires comparison with a state-of-the-art classical simulator. We report HPC simulations of hard random quantum circuits (RQC), which have been recently used as a benchmark for the first experimental demonstration of Quantum Supremacy, sustaining an average performance of 281 Pflop/s (true single precision) on Summit, currently the fastest supercomputer in the World. These simulations were carried out using qFlex, a tensor-network-based classical high-performance simulator of RQCs. Our results show an advantage of many orders of magnitude in energy consumption of NISQ devices over classical supercomputers. In addition, we propose a standard benchmark for NISQ computers based on qFlex., Comment: The paper has been published in Quantum Science and Technology

The Quantum Alternating Operator Ansatz (QAOA) is a promising gate-model meta-heuristic for combinatorial optimization. Applying the algorithm to problems with constraints presents an implementation challenge for near-term quantum resources. This work explores strategies for enforcing hard constraints by using $XY$-Hamiltonians as mixing operators (mixers). Despite the complexity of simulating the $XY$ model, we demonstrate that for problems represented through one-hot-encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O(\kappa)$ where $\kappa$ is the number of assignable colors. We also specify general strategies for implementing QAOA circuits on all-to-all connected hardware graphs and linearly connected hardware graphs inspired by fermionic simulation techniques. Performance is validated on graph coloring problems that are known to be challenging for a given classical algorithm. The general strategy of using $XY$-mixers is borne out numerically, demonstrating a significant improvement over the general $X$-mixer, and moreover the generalized $W$-state yields better performance than easier-to-generate classical initial states when $XY$ mixers are used., Comment: Updated to journal version. Detailed W-state generating unitaries in Appendix C.1

We investigate alternative annealing schedules on the current generation of quantum annealing hardware (the D-Wave 2000Q), which includes the use of forward and reverse annealing with an intermediate pause. This work provides new insights into the inner workings of these devices (and quantum devices in general), particular into how thermal effects govern the system dynamics. We show that a pause mid-way through the anneal can cause a dramatic change in the output distribution, and we provide evidence suggesting thermalization is indeed occurring during such a pause. We demonstrate that upon pausing the system in a narrow region shortly after the minimum gap, the probability of successfully finding the ground state of the problem Hamiltonian can be increased over an order of magnitude. We relate this effect to relaxation (i.e. thermalization) after diabatic and thermal excitations that occur in the region near to the minimum gap. For a set of large-scale problems of up to 500 qubits, we demonstrate that the distribution returned from the annealer very closely matches a (classical) Boltzmann distribution of the problem Hamiltonian, albeit one with a temperature at least 1.5 times higher than the (effective) temperature of the annealer. Moreover, we show that larger problems are more likely to thermalize to a classical Boltzmann distribution., Comment: 16+6 pages, 19+10 figures. v2: updated to published version; minor changes throughout, new figure in appendix

We present the mapping of a class of simplified air traffic management (ATM) problems (strategic conflict resolution) to quadratic unconstrained boolean optimization (QUBO) problems. The mapping is performed through an original representation of the conflict-resolution problem in terms of a conflict graph, where nodes of the graph represent flights and edges represent a potential conflict between flights. The representation allows a natural decomposition of a real world instance related to wind-optimal trajectories over the Atlantic ocean into smaller subproblems, that can be discretized and are amenable to be programmed in quantum annealers. In the study, we tested the new programming techniques and we benchmark the hardness of the instances using both classical solvers and the D-Wave 2X and D-Wave 2000Q quantum chip. The preliminary results show that for reasonable modeling choices the most challenging subproblems which are programmable in the current devices are solved to optimality with 99% of probability within a second of annealing time., Comment: Paper accepted for publication on: IEEE Transactions on Intelligent Transportation Systems

The next few years will be exciting as prototype universal quantum processors emerge, enabling implementation of a wider variety of algorithms. Of particular interest are quantum heuristics, which require experimentation on quantum hardware for their evaluation, and which have the potential to significantly expand the breadth of quantum computing applications. A leading candidate is Farhi et al.'s Quantum Approximate Optimization Algorithm, which alternates between applying a cost-function-based Hamiltonian and a mixing Hamiltonian. Here, we extend this framework to allow alternation between more general families of operators. The essence of this extension, the Quantum Alternating Operator Ansatz, is the consideration of general parametrized families of unitaries rather than only those corresponding to the time-evolution under a fixed local Hamiltonian for a time specified by the parameter. This ansatz supports the representation of a larger, and potentially more useful, set of states than the original formulation, with potential long-term impact on a broad array of application areas. For cases that call for mixing only within a desired subspace, refocusing on unitaries rather than Hamiltonians enables more efficiently implementable mixers than was possible in the original framework. Such mixers are particularly useful for optimization problems with hard constraints that must always be satisfied, defining a feasible subspace, and soft constraints whose violation we wish to minimize. More efficient implementation enables earlier experimental exploration of an alternating operator approach to a wide variety of approximate optimization, exact optimization, and sampling problems. Here, we introduce the Quantum Alternating Operator Ansatz, lay out design criteria for mixing operators, detail mappings for eight problems, and provide brief descriptions of mappings for diverse problems., Comment: 51 pages, 2 figures. Revised to match journal paper

Farhi et al. recently proposed a class of quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA), for approximately solving combinatorial optimization problems. A level-p QAOA circuit consists of p steps; in each step a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The 2p times for which these two Hamiltonians are applied are the parameters of the algorithm, which are to be optimized classically for the best performance. As p increases, parameter optimization becomes inefficient due to the curse of dimensionality. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here, we analytically and numerically study parameter setting for QAOA applied to MaxCut. For level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher p could be derived, but the number of terms quickly becomes prohibitive. For a special case of MaxCut, the ring of disagrees, or the 1D antiferromagnetic ring, we provide an analysis for arbitrarily high level. Using a fermionic representation, the evolution of the system under QAOA translates into quantum control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of QAOA for any p. It also greatly simplifies numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional sub-manifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima., Comment: Correction: A missing factor of 2 in Eq. (14) of Theorem 1 has been inserted, and a sign error in Eq. (A11) has been fixed

By contrasting the performance of two quantum annealers operating at different temperatures, we address recent questions related to the role of temperature in these devices and their function as `Boltzmann samplers'. Using a method to reliably calculate the degeneracies of the energy levels of large-scale spin-glass instances, we are able to estimate the instance-dependent effective temperature from the output of annealing runs. Our results show that the output distributions of the annealers do not in general correspond to classical Boltzmann distributions. For the small fraction of the instances for which classical thermalization takes place, we find that the effective temperatures are significantly higher than the physical temperatures. Our results in this regime provide further evidence for the `freeze-out' picture in which the output is sampled from equilibrium distributions determined at a point in time earlier in the quantum annealing process. We also find that the effective temperatures at different programming cycles fluctuate greatly, with the effect worsening with problem size. We discuss the implications of our results for the design of future quantum annealers to act as efficient Boltzmann samplers and for the programming of such annealers., Comment: 12 pages, 16 figures. v2: updated to published version

Inspired by a class of algorithms proposed by Farhi et al. (arXiv:1411.4028), namely the quantum approximate optimization algorithm (QAOA), we present a circuit-based quantum algorithm to search for a needle in a haystack, obtaining the same quadratic speedup achieved by Grover's original algorithm. In our algorithm, the problem Hamiltonian (oracle) and a transverse field are applied alternately to the system in a periodic manner. We introduce a technique, based on spin-coherent states, to analyze the composite unitary in a single period. This composite unitary drives a closed transition between two states that have high degrees of overlap with the initial state and the target state, respectively. The transition rate in our algorithm is of order $\Theta(1/\sqrt N)$, and the overlaps are of order $\Theta(1)$, yielding a nearly optimal query complexity of $T\simeq \sqrt N (\pi/2\sqrt 2\,)$. Our algorithm is a QAOA circuit that demonstrates a quantum advantage with a large number of iterations that is not derived from Trotterization of an adiabatic quantum optimization (AQO) algorithm. It also suggests that the analysis required to understand QAOA circuits involves a very different process from estimating the energy gap of a Hamiltonian in AQO., Comment: 9 pages, 4 figures

We address Gillis' recent criticism [arXiv:1506.05795] of a series of papers (by different combinations of the present authors) on formulations of Bell's theorem. Those papers intended to address an unfortunate gap of communication between two broad camps in the quantum foundations community that we identify as "operationalists" and "realists". Here, we once again urge the readers to approach the question from an unbiased standpoint, and explain that Gillis' criticism draws too heavily on the philosophical inclinations of one side of that debate -- the realist camp. As part of that explanation we discuss intuition versus proof, look again at Bell's formalizations of locality, and correct misstatements by Gillis of our views, and those of Bell and Einstein., Comment: 10 pages. To be published in International Journal of Quantum Foundations

Physical constraints make it challenging to implement and control many-body interactions. For this reason, designing quantum information processes with Hamiltonians consisting of only one- and two-local terms is a worthwhile challenge. Enabling error suppression with two-local Hamiltonians is particularly challenging. A no-go theorem of Marvian and Lidar [Physical Review Letters 113(26), 260504 (2014)] demonstrates that, even allowing particles with high Hilbert-space dimension, it is impossible to protect quantum information from single-site errors by encoding in the ground subspace of any Hamiltonian containing only commuting two-local terms. Here, we get around this no-go result by encoding in the ground subspace of a Hamiltonian consisting of non-commuting two-local terms arising from the gauge operators of a subsystem code. Specifically, we show how to protect stored quantum information against single-qubit errors using a Hamiltonian consisting of sums of the gauge generators from Bacon-Shor codes [Physical Review A 73(1), 012340 (2006)] and generalized-Bacon-Shor code [Physical Review A 83(1), 012320 (2011)]. Our results imply that non-commuting two-local Hamiltonians have more error-suppressing power than commuting two-local Hamiltonians. While far from providing full fault tolerance, this approach improves the robustness achievable in near-term implementable quantum storage and adiabatic quantum computations, reducing the number of higher-order terms required to encode commonly used adiabatic Hamiltonians such as the Ising Hamiltonians common in adiabatic quantum optimization and quantum annealing., Comment: 25 pages, 9 figures

Yes. That is my polemical reply to the titular question in Travis Norsen's self-styled "polemical response to Howard Wiseman's recent paper." Less polemically, I am pleased to see that on two of my positions --- that Bell's 1964 theorem is different from Bell's 1976 theorem, and that the former does not include Bell's one-paragraph heuristic presentation of the EPR argument --- Norsen has made significant concessions. In his response, Norsen admits that "Bell's recapitulation of the EPR argument in [the relevant] paragraph leaves something to be desired," that it "disappoints" and is "problematic". Moreover, Norsen makes other statements that imply, on the face of it, that he should have no objections to the title of my recent paper ("The Two Bell's Theorems of John Bell"). My principle aim in writing that paper was to try to bridge the gap between two interpretational camps, whom I call 'operationalists' and 'realists', by pointing out that they use the phrase "Bell's theorem" to mean different things: his 1964 theorem (assuming locality and determinism) and his 1976 theorem (assuming local causality), respectively. Thus, it is heartening that at least one person from one side has taken one step on my bridge. That said, there are several issues of contention with Norsen, which we (the two authors) address after discussing the extent of our agreement with Norsen. The most significant issues are: the indefiniteness of the word 'locality' prior to 1964; and the assumptions Einstein made in the paper quoted by Bell in 1964 and their relation to Bell's theorem., Comment: 13 pages (arXiv version) in http://www.ijqf.org/archives/2093

We report on a case study in programming an early quantum annealer to attack optimization problems related to operational planning. While a number of studies have looked at the performance of quantum annealers on problems native to their architecture, and others have examined performance of select problems stemming from an application area, ours is one of the first studies of a quantum annealer's performance on parametrized families of hard problems from a practical domain. We explore two different general mappings of planning problems to quadratic unconstrained binary optimization (QUBO) problems, and apply them to two parametrized families of planning problems, navigation-type and scheduling-type. We also examine two more compact, but problem-type specific, mappings to QUBO, one for the navigation-type planning problems and one for the scheduling-type planning problems. We study embedding properties and parameter setting, and examine their effect on the efficiency with which the quantum annealer solves these problems. From these results we derive insights useful for the programming and design of future quantum annealers: problem choice, the mapping used, the properties of the embedding, and the annealing profile all matter, each significantly affecting the performance., Comment: 19 pages, 16 figures. Comments welcome

We consider the issue of what should count as a resource for measurement-based quantum computation (MBQC). While a state that supports universal quantum computation clearly should be considered a resource, universality should not be necessary given the existence of interesting, but less computationally-powerful, classes of MBQCs. Here, we propose minimal criteria for a state to be considered a resource state for MBQC. Using these criteria, we explain why discord-free states cannot be resources for MBQC, contrary to recent claims [Hoban et al., arXiv:1304.2667v1]. Independently of our criteria, we also show that the arguments of Hoban et al., if correct, would imply that Shor's algorithm (for example) can be implemented by measuring discord-free states., Comment: 7 pages. Title changed again at request of editors. Significant expository changes. Technical content the same as before

The success of the abstract model of computation, in terms of bits, logical operations, programming language constructs, and the like, makes it easy to forget that computation is a physical process. Our cherished notions of computation and information are grounded in classical mechanics, but the physics underlying our world is quantum. In the early 80s researchers began to ask how computation would change if we adopted a quantum mechanical, instead of a classical mechanical, view of computation. Slowly, a new picture of computation arose, one that gave rise to a variety of faster algorithms, novel cryptographic mechanisms, and alternative methods of communication. Small quantum information processing devices have been built, and efforts are underway to build larger ones. Even apart from the existence of these devices, the quantum view on information processing has provided significant insight into the nature of computation and information, and a deeper understanding of the physics of our universe and its connections with computation. We start by describing aspects of quantum mechanics that are at the heart of a quantum view of information processing. We give our own idiosyncratic view of a number of these topics in the hopes of correcting common misconceptions and highlighting aspects that are often overlooked. A number of the phenomena described were initially viewed as oddities of quantum mechanics. It was quantum information processing, first quantum cryptography and then, more dramatically, quantum computing, that turned the tables and showed that these oddities could be put to practical effect. It is these application we describe next. We conclude with a section describing some of the many questions left for future work, especially the mysteries surrounding where the power of quantum information ultimately comes from., Comment: Invited book chapter for Computation for Humanity - Information Technology to Advance Society to be published by CRC Press. Concepts clarified and style made more uniform in version 2. Many thanks to the referees for their suggestions for improvements

In this article, we show how to map a sampling of the hardest artificial intelligence problems in space exploration onto equivalent Ising models that then can be attacked using quantum annealing implemented in D-Wave machine. We overview the existing results as well as propose new Ising model implementations for quantum annealing. We review supervised and unsupervised learning algorithms for classification and clustering with applications to feature identification and anomaly detection. We introduce algorithms for data fusion and image matching for remote sensing applications. We overview planning problems for space exploration mission applications and algorithms for diagnostics and recovery with applications to deep space missions. We describe combinatorial optimization algorithms for task assignment in the context of autonomous unmanned exploration. Finally, we discuss the ways to circumvent the limitation of the Ising mapping using a "blackbox" approach based on ideas from probabilistic computing. In this article we describe the architecture of the D-Wave One machine and report its benchmarks. Results on random ensemble of problems in the range of up to 96 qubits show improved scaling for median core quantum annealing time compared with classical algorithms; whether this scaling persists for larger problem sizes is an open question. We also review previous results of D-Wave One benchmarking studies for solving binary classification problems with a quantum boosting algorithm which is shown to outperform AdaBoost. We review quantum algorithms for structured learning for multi-label classification and introduce a hybrid classical/quantum approach for learning the weights. Results of D-Wave One benchmarking studies for learning structured labels on four different data sets show a better performance compared with an independent Support Vector Machine approach with linear kernel., Comment: 69 pages, 29 figures; corrected affiliations and acknowledgements, added some details, fixed typos

Creating virtual models of real spaces and objects is cumbersome and time consuming. This paper focuses on the problem of geometric reconstruction from sparse data obtained from certain image-based modeling approaches. A number of elegant and simple-to-state problems arise concerning when the geometry can be reconstructed. We describe results and counterexamples, and list open problems.

Faster algorithms, novel cryptographic mechanisms, and alternative methods of communication become possible when the model underlying information and computation changes from a classical mechanical model to a quantum mechanical one. Quantum algorithms perform a select set of tasks vastly more efficiently than any classical algorithm, but for many tasks it has been proved that quantum algorithms provide no advantage. The breadth of quantum computing applications is still being explored. Major application areas include security and the many fields that would benefit from efficient quantum simulation. The quantum information processing viewpoint provides insight into classical algorithmic issues as well as a deeper understanding of entanglement and other non-classical aspects of quantum physics. This overview is aimed at technology managers who wish to gain a high level understanding of quantum information processing, particularly quantum computing., Comment: Final version of entry on quantum computing for Wiley's Handbook of Technology Management. Glossary added. Many relatively minor changes throughout. Many thanks to the excellent referees!

This survey, aimed at information processing researchers, highlights intriguing but lesser known results, corrects misconceptions, and suggests research areas. Themes include: certainty in quantum algorithms; the "fewer worlds" theory of quantum mechanics; quantum learning; probability theory versus quantum mechanics., Comment: Invited paper accompanying invited talk to AAAI Spring Symposium 2007. Comments, corrections, and suggestions would be most welcome

This paper is a more succinct version of the author's 1993 UCLA mathematics thesis. It proves that any group quasi-isometric to the product of the hyperbolic plane with the real line is a finite extension of a cocompact lattice in either the isometry group of the product of the hyperbolic plane with the real line or the isometry group of the universal cover of SL(2,R)., Comment: Journal of the London Math Society, to appear. Minor revisions and updated references. 19 pages

Richard Feynman's observation that quantum mechanical effects could not be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used quantum effects. This speculation appeared justified when Peter Shor described a polynomial time quantum algorithm for factoring integers. In quantum systems, the computational space increases exponentially with the size of the system which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new non-traditional programming techniques. The aim of this paper is to guide computer scientists and other non-physicists through the conceptual and notational barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to harnessing the power of quantum parallelism are explained, including Shor's algorithm, Grover's algorithm, and Hogg's algorithms. We conclude with a discussion of quantum error correction., Comment: 45 pages. To appear in ACM Computing Surveys. LATEX file. Exposition improved throughout thanks to reviewers' comments

We investigate alternative annealing schedules on the current generation of quantum annealing hardware (the D-Wave 2000Q), which includes the use of forward and reverse annealing with an- intermediate pause. This work provides new insights into the inner workings of these devices (and quantum devices in general), particular into how thermal effects govern the system dynamics. We show that a pause mid-way through the anneal can cause a dramatic change in the output distribution, and we provide evidence suggesting thermalization is indeed occurring during such a pause. We demonstrate that upon pausing the system in a narrow region shortly after the minimum gap, the probability of successfully finding the ground state of the problem Hamiltonian can be increased by several orders of magnitude. We relate this effect to relaxation (i.e. thermalization) after diabatic and thermal excitations that occur in the region near to the minimum gap. For a set of large-scale problems of up to 500 qubits, we demonstrate that the distribution returned from the annealer very closely matches a (classical) Boltzmann distribution of the problem Hamiltonian, albeit one with a temperature at least 1.5 times higher than the (effective) temperature of the device. Moreover, we show that larger problems are more likely to thermalize to a classical Boltzmann distribution.

Network-related connectivity optimization problems are underlying a wide range of applications and are also of high computational complexity. We consider studying network optimization problems using two types of quantum heuristics.One is quantum annealing, and the other Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms for gate-model quantum computation, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present problem mappings for problems of finding the spanning-tree or spanning-graph of a graph that optimizes certain costs, and a variant that further requires the spanning-tree be degree-bounded. With quantum annealing, all constraints are cast into penalty terms in the cost Hamiltonian, and the solution is encoded as the ground state of the Hamiltonian. We provide three mappings to the quadratic unconstrained binary optimization (QUBO) form, compare the resource requirements, and analyze the tradeoffs. For QAOA, we give special focus on the design of mixers based on the constraints presented in the problem, such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such hard constraint is that a mixer applied to a spanning-tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.