Search

Motivated by recent experiments in which specific thermal properties of complex many-body systems were successfully reproduced on a commercially available quantum annealer, we examine the extent to which quantum annealing hardware can reliably sample from the thermal state in a specific basis associated with a target quantum Hamiltonian. We address this question by studying the diagonal thermal properties of the canonical one-dimensional transverse-field Ising model on a D-Wave 2000Q quantum annealing processor. We find that the quantum processor fails to produce the correct expectation values predicted by Quantum Monte Carlo. Comparing to master equation simulations, we find that this discrepancy is best explained by how the measurements at finite transverse fields are enacted on the device. Specifically, measurements at finite transverse field require the system to be quenched from the target Hamiltonian to a Hamiltonian with negligible transverse field, and this quench is too slow. The limitations imposed by such hardware make it an unlikely candidate for thermal sampling, and it remains an open question what thermal expectation values can be robustly estimated in general for arbitrary quantum many-body systems., v2: Updated to published version. 13 pages, 13 figures

A novel quantum-classical hybrid scheme is proposed to efficiently solve large-scale combinatorial optimization problems. The key concept is to introduce a Hamiltonian dynamics of the classical flux variables associated with the quantum spins of the transverse-field Ising model. Molecular dynamics of the classical fluxes can be used as a powerful preconditioner to sort out the frozen and ambivalent spins for quantum annealers. The performance and accuracy of our smooth hybridization in comparison to the standard classical algorithms (the tabu search and the simulated annealing) are demonstrated by employing the MAX-CUT and Ising spin-glass problems., 14 pages, 10 figures; v2: 17 pages, 14 figures, supplementary note added, to be published in Scientific Reports

Emerging quantum processors provide an opportunity to explore new approaches for solving traditional problems in the post Moore’s law supercomputing era. However, the limited number of qubits makes it infeasible to tackle massive real-world datasets directly in the near future, leading to new challenges in utilizing these quantum processors for practical purposes. Hybrid quantum-classical algorithms that leverage both quantum and classical types of devices are considered as one of the main strategies to apply quantum computing to large-scale problems. In this article, we advocate the use of multilevel frameworks for combinatorial optimization as a promising general paradigm for designing hybrid quantum-classical algorithms. To demonstrate this approach, we apply this method to two well-known combinatorial optimization problems, namely, the Graph Partitioning Problem, and the Community Detection Problem. We develop hybrid multilevel solvers with quantum local search on D-Wave’s quantum annealer and IBM’s gate-model based quantum processor. We carry out experiments on graphs that are orders of magnitude larger than the current quantum hardware size, and we observe results comparable to state-of-the-art solvers in terms of quality of the solution. Reproducibility : Our code and data are available at Reference [1].

The promise of quantum computing lies in harnessing programmable quantum devices for practical applications such as efficient simulation of quantum materials and condensed matter systems. One important task is the simulation of geometrically frustrated magnets in which topological phenomena can emerge from competition between quantum and thermal fluctuations. Here we report on experimental observations of equilibration in such simulations, measured on up to 1440 qubits with microsecond resolution. By initializing the system in a state with topological obstruction, we observe quantum annealing (QA) equilibration timescales in excess of one microsecond. Measurements indicate a dynamical advantage in the quantum simulation compared with spatially local update dynamics of path-integral Monte Carlo (PIMC). The advantage increases with both system size and inverse temperature, exceeding a million-fold speedup over an efficient CPU implementation. PIMC is a leading classical method for such simulations, and a scaling advantage of this type was recently shown to be impossible in certain restricted settings. This is therefore an important piece of experimental evidence that PIMC does not simulate QA dynamics even for sign-problem-free Hamiltonians, and that near-term quantum devices can be used to accelerate computational tasks of practical relevance., Experimental demonstration of quantum speedup that scales with the system size is the goal of near-term quantum computing. Here, the authors demonstrate such scaling advantage for a D-Wave quantum annealer over analogous classical algorithms in simulations of frustrated quantum magnets.

Various sources of noise limit the performance of quantum computers by altering qubit states in an uncontrolled manner throughout computations and reducing their coherence time. In quantum annealers, this noise introduces additional fluctuations to the parameters defining the original problem Hamiltonian, such that they find the ground states of problems perturbed from those originally programmed. Here we describe a method to benchmark the amount of noise affecting the programmed Hamiltonian of a quantum annealer. We show that a sequence of degenerate runs with the coefficients of the programmed Hamiltonian set to zero leads to an estimate of the noise spectral density affecting Hamiltonian parameters "in situ" during the quantum annealing protocol. The method is demonstrated in D-Wave's lower noise 2000 qubit device (DW_2000Q_6) and in its recently released 5000 qubit device (Advantage_system1.1). Our benchmarking of DW_2000Q_6 shows Hamiltonian noise dominated by the $1/f^{0.7}$ frequency dependence characteristic of flux noise intrinsic to the materials forming flux qubits. In contrast, Advantage_system1.1 is found to be affected by additional noise sources for low annealing times, with underlying intrinsic flux noise amplitudes $2-3$ times higher than in DW_2000Q_6 for all annealing times., 6 pages, 4 figures, accepted for oral presentation at IEEE 2020 International Conference on Quantum Computing and Engineering, accepted for publication in IEEE Transactions on Quantum Engineering

In recent years, the urbanization process has brought modernity while also causing key issues, such as traffic congestion and parking conflicts. Therefore, cities need a more intelligent "brain" to form more intelligent and efficient transportation systems. At present, as a type of machine learning, the traditional clustering algorithm still has limitations. K-means algorithm is widely used to solve traffic clustering problems, but it has limitations, such as sensitivity to initial points and poor robustness. Therefore, based on the hybrid architecture of Quantum Annealing (QA) and brain-inspired cognitive computing, this study proposes QA and Brain-Inspired Clustering Algorithm (QABICA) to solve the problem of urban taxi-stand locations. Based on the traffic trajectory data of Xi'an and Chengdu provided by Didi Chuxing, the clustering results of our algorithm and K-means algorithm are compared. We find that the average taxi-stand location bias of the final result based on QABICA is smaller than that based on K-means, and the bias of our algorithm can effectively reduce the tradition K-means bias by approximately 42%, up to approximately 83%, with higher robustness. QA algorithm is able to jump out of the local suboptimal solutions and approach the global optimum, and brain-inspired cognitive computing provides search feedback and direction. Thus, we will further consider applying our algorithm to analyze urban traffic flow, and solve traffic congestion and other key problems in intelligent transportation.

Traveling Salesman Problem (TSP) is a combinatorial optimization problem, which has NP-Complete (NPC) complexity. At present, there is no exact algorithm to solve similar problems, only an approximate algorithm to simplify the problem can be found. For example, quantum annealing algorithm (QA) can play such a role. QA transforms the distance matrix sum of TSP into Pauli matrix, adds a transverse magnetic field to realize the quantum tunneling effect, reduces the energy needed to cross the barrier, and reduces the number of iterations to find the optimal solution. However, although the QA has fewer iteration steps, it usually produces errors. In this context, this paper’s INQA improves the QA. In this paper, the theoretical basis of quantum annealing algorithm is introduced, aiming at the shortcomings of quantum annealing algorithm in solving TSP problem, a new algorithm INQA is proposed, and it is verified by experiments. In the case of high initial temperature, the INQA has larger search range and more active search. Meanwhile, with the decrease of temperature, the search range is reduced, and the accuracy of the algorithm is improved. In fact, QA in this paper is a quantum annealing method for simulation.

It is extremely challenging to solve the mixed-integer optimal control problems (MIOCPs) due to the complex computation in solving the integer decision variables. This paper presents a new method based on quantum annealing (QA) to solve MIOCP. The QA is a metaheuristic which applies quantum tunneling in the annealing process. It has a faster convergence speed in optimal-searching and is less likely to run into local minima. Hence, QA is applied to deal with this kind of optimization problems. First, MIOCP is transformed into a mixed-integer nonlinear programming (MINLP). Then, a method based on QA is adopted to solve the MINLP and acquire the optimal solution. At last, two benchmark examples including Lotka-Volterra type fishing problem and distillation column are presented and solved. The effectiveness of the methodology is verified by the acquired optimal schemes.

With quantum computers still under heavy development, already numerous quantum machine learning algorithms have been proposed for both gate-based quantum computers and quantum annealers. Recently, a quantum annealing version of a reinforcement learning algorithm for grid-traversal using one agent was published. We extend this work based on quantum Boltzmann machines, by allowing for any number of agents. We show that the use of quantum annealing can improve the learning compared to classical methods. We do this both by means of actual quantum hardware and by simulated quantum annealing.

The effect of uniformly distributed fluctuation in the coupling strength of a 100 spins transverse field quantum Ising chain is studied using the Density Matrix Renormalization Group on the Matrix Product States formalism. Uniform noise with mean zero and amplitude η is introduced to uniform nearest neighbour coupling of value unity. Disordered averages of thermodynamic quantities are calculated from 100 disordered realizations for each transverse field reading. We show that the system exhibits distinct behaviour of ordered and disordered state separated at η~1.0. For η ≲ 1.0, thermodynamic behaviour of the system gradually deviates from pure quantum Ising model. For η > 1.0 system exhibits highly fluctuating thermodynamic behaviour. Edward-Anderson order parameters are calculated and shown to be much less fluctuating and suitable as an order parameter for η > 1.0. Qualitative behaviour of the system is not affected by finite-size effect and replacing the fluctuation with normally distributed noise. Finally, for noise level between η = 1.0 and 1.5, the system exhibits a faster phase transition and enhances transverse magnetization before the critical point. For certain ranges of noise amplitude before the critical point, the quantum fluctuations are amplified. This suggests a potential improvement of quantum annealing within that regime.

Optimization is one of the key applications of quantum computing where a quantum speedup has been an eagerly anticipated outcome. A promising approach to optimization using quantum dynamics is to consider a linear combination $s(t)B+[1\ensuremath{-}s(t)]C$ of two noncommuting Hamiltonians $B$ and $C$, where $C$ encodes the solution to the optimization problem in its ground state, $B$ is a Hamiltonian whose ground state is easy to prepare, and $s(t)\ensuremath{\in}[0,1]$ is the bounded ``switching schedule'' or ``path,'' with $t\ensuremath{\in}[0,{t}_{f}]$. This approach encompasses two of the most widely studied quantum-optimization algorithms: quantum annealing [QA; continuous $s(t)$] and the quantum approximate optimization algorithm [QAOA; piecewise constant $s(t)$]. While it is notoriously difficult to prove a quantum advantage for either algorithm, it is possible to compare and contrast them by finding the optimal $s(t)$. Here we provide a rigorous analysis of this quantum optimal control problem, entirely within the geometric framework of Pontryagin's maximum principle of optimal control theory. We extend earlier results, derived in a purely closed-system setting, to open systems. This is the natural setting for experimental realizations of QA and QAOA. In the closed-system setting it was shown that the optimal solution is a ``bang-anneal-bang'' schedule, with the bangs characterized by $s(t)=0$ and $s(t)=1$ in finite subintervals of $[0,{t}_{f}]$, in particular, $s(0)=0$ and $s({t}_{f})=1$, in contrast to the standard prescription $s(0)=1$ and $s({t}_{f})=0$ of QA. As an example, we prove that for a single spin-$1/2$, the optimal solution in the closed-system setting is the bang-bang schedule, switching midway from $s\ensuremath{\equiv}0$ to $s\ensuremath{\equiv}1$. For finite-dimensional environments and without any approximations we identify sufficient conditions ensuring that either the bang-anneal, anneal-bang, or bang-anneal-bang schedules are optimal, and recover the optimality of $s(0)=0$ and $s({t}_{f})=1$. However, for infinite-dimensional environments and a system described by an adiabatic Redfield master equation we do not recover the bang-type optimal solution. In fact we can only identify conditions under which $s({t}_{f})=1$, and even this result is not recovered in the fully Markovian limit, suggesting that the pure anneal-type schedule is optimal. Our open-system results have implications for the use of experimental quantum-information processors, which are by necessity noisy, and suggest that in this practical sense the optimal schedules for quantum optimization are likely to be continuous.

We present experiments in solving combinatorial optimization and constraint satisfaction problems by means of Quantum Annealing. We describe how to model classic constraint problems such as N-queens and Magic Square as well as hard combinatorial problems such as the Costas Array Problem or the Quadratic Assignment Problem in terms of QUBO (Quadratic Unconstrained Binary Optimization). QUBO is the input language of quantum computers based on quantum annealing such as the D-Wave systems and of the ”quantum-inspired” but classical devices such as Fujitsu’s Digital Annealing Unit or Hitachi’s CMOS Annealing Machine. We present preliminary results for solving these combinatorial optimization and constraint satisfaction problems by implementation on the D-Wave quantum computer.

In order to solve real world combinatorial optimization problems with a D-Wave quantum annealer it is necessary to embed the problem at hand into the D-Wave hardware graph, namely Chimera or Pegasus. Most hard real world problems exhibit a strong connectivity. For the worst case scenario of a complete graph, there exists an efficient solution for the embedding into the ideal Chimera graph. However, since real machines almost always have broken qubits it is necessary to find an embedding into the broken hardware graph. We present a new approach to the problem of embedding complete graphs into broken Chimera graphs. This problem can be formulated as an optimization problem, more precisely as a matching problem with additional linear constraints. Although being NP-hard in general it is fixed parameter tractable in the number of inaccessible vertices in the Chimera graph. We tested our exact approach on various instances of broken hardware graphs, both related to real hardware as well as randomly generated. For fixed runtime, we were able to embed larger complete graphs compared to previous, heuristic approaches. As an extension, we developed a fast heuristic algorithm which enables us to solve even larger instances. We compared the performance of our heuristic and exact approaches., Comment: 26 pages, 9 figures, 2 tables

We construct an Ising Hamiltonian with an engineered energy landscape such that it has a local energy minimum which is near the true global minimum solution and further away from a false minimum. Using a technique established in previous experiments, we design our experiment such that (at least on timescales relevant to our study) the false minimum is reached preferentially in forward annealing due to high levels of quantum fluctuations. This allows us to demonstrate the key principle of reverse annealing, that the solution space can be searched locally, preferentially finding nearby solutions, even in the presence of a false minimum. The techniques used here are distinct from previously used experimental techniques and allow us to probe the fundamental search range of the device in an alternative way. We perform these experiments on two flux qubit quantum annealers, one with higher noise levels than the other. We find evidence that the lower noise device is more likely to find the more distant energy minimum (the false minimum in this case), suggesting that reducing noise fundamentally increases the range over which flux qubit quantum annealers are able to search. Our work explains why reducing the noise leads to improved performance on these quantum annealers. This supports the idea that these devices may be able to search over broad regions of the solution space quickly, one of the core reasons why quantum annealers are viewed as a potential avenue for a quantum computational advantage.

The quantum approximate optimization algorithm (QAOA) is a prospective near-term quantum algorithm due to its modest circuit depth and promising benchmarks. However, an external parameter optimization required in QAOA could become a performance bottleneck. This motivates studies of the optimization landscape and search for heuristic ways of parameter initialization. In this work we visualize the optimization landscape of the QAOA applied to the MaxCut problem on random graphs, demonstrating that random initialization of the QAOA is prone to converging to local minima with sub-optimal performance. We introduce the initialization of QAOA parameters based on the Trotterized quantum annealing (TQA) protocol, parameterized by the Trotter time step. We find that the TQA initialization allows to circumvent the issue of false minima for a broad range of time steps, yielding the same performance as the best result out of an exponentially scaling number of random initializations. Moreover, we demonstrate that the optimal value of the time step coincides with the point of proliferation of Trotter errors in quantum annealing. Our results suggest practical ways of initializing QAOA protocols on near-term quantum devices and reveals new connections between QAOA and quantum annealing., Comment: 10 pages, 9 figures; typos corrected, references added

Generative models have the capacity to model and generate new examples from a dataset and have an increasingly diverse set of applications driven by commercial and academic interest. In this work, we present an algorithm for learning a latent variable generative model via generative adversarial learning where the canonical uniform noise input is replaced by samples from a graphical model. This graphical model is learned by a Boltzmann machine which learns low-dimensional feature representation of data extracted by the discriminator. A quantum processor can be used to sample from the model to train the Boltzmann machine. This novel hybrid quantum-classical algorithm joins a growing family of algorithms that use a quantum processor sampling subroutine in deep learning, and provides a scalable framework to test the advantages of quantum-assisted learning. For the latent space model, fully connected, symmetric bipartite and Chimera graph topologies are compared on a reduced stochastically binarized MNIST dataset, for both classical and quantum sampling methods. The quantum-assisted associative adversarial network successfully learns a generative model of the MNIST dataset for all topologies. Evaluated using the Fréchet inception distance and inception score, the quantum and classical versions of the algorithm are found to have equivalent performance for learning an implicit generative model of the MNIST dataset. Classical sampling is used to demonstrate the algorithm on the LSUN bedrooms dataset, indicating scalability to larger and color datasets. Though the quantum processor used here is a quantum annealer, the algorithm is general enough such that any quantum processor, such as gate model quantum computers, may be substituted as a sampler.

Restricted Boltzmann Machine (RBM) is an energy-based, undirected graphical model. It is commonly used for unsupervised and supervised machine learning. Typically, RBM is trained using contrastive divergence (CD). However, training with CD is slow and does not estimate the exact gradient of the log-likelihood cost function. In this work, the model expectation of gradient learning for RBM has been calculated using a quantum annealer (D-Wave 2000Q), where obtaining samples is faster than Markov chain Monte Carlo (MCMC) used in CD. Training and classification results of RBM trained using quantum annealing are compared with the CD-based method. The performance of the two approaches is compared with respect to the classification accuracies, image reconstruction, and log-likelihood results. The classification accuracy results indicate comparable performances of the two methods. Image reconstruction and log-likelihood results show improved performance of the CD-based method. It is shown that the samples obtained from quantum annealer can be used to train an RBM on a 64-bit “bars and stripes” dataset with classification performance similar to an RBM trained with CD. Though training based on CD showed improved learning performance, training using a quantum annealer could be useful as it eliminates computationally expensive MCMC steps of CD.

High-energy physics is replete with hard computational problems and it is one of the areas where quantum computing could be used to speed up calculations. We present an implementation of likelihood-based regularized unfolding on a quantum computer. The inverse problem is recast in terms of quadratic unconstrained binary optimization (QUBO), which has the same form of the Ising hamiltonian and hence it is solvable on a programmable quantum annealer. We tested the method using a model that captures the essence of the problem, and compared the results with a baseline method commonly used in precision measurements at the Large Hadron Collider (LHC) at CERN. The unfolded distribution is in very good agreement with the original one. We also show how the method can be extended to include the effect of nuisance parameters representing sources of systematic uncertainties affecting the measurement.

Finding a Hadamard matrix (H-matrix) among the set of all binary matrices of corresponding order is a hard problem, which potentially can be solved by quantum computing. We propose a method to formulate the Hamiltonian of finding H-matrix problem and address its implementation limitation on existing quantum annealing machine (QAM) that allows up to quadratic terms, whereas the problem naturally introduces higher order ones. For an M-order H-matrix, such a limitation increases the number of variables from M^2 to (M^3 +M^2-M)/2, which makes the formulation of the Hamiltonian too exhaustive to do by hand. We use symbolic computing techniques to manage this problem. Three related cases are discussed: (1) finding N < M orthogonal binary vectors, (2) finding M-orthogonal binary vectors, which is equivalent to finding a H-matrix, and (3) finding N-deleted vectors of an M-order H-matrix. Solutions of the problems by a 2-body simulated annealing software and by an actual quantum annealing hardware are also discussed., 21 pages, 4 figures

Adiabatic quantum computation (AQC) is a promising counterpart of universal quantum computation, based on the key concept of quantum annealing (QA). QA is claimed to be at the basis of commercial quantum computers and benefits from the fact that the detrimental role of decoherence and dephasing seems to have poor impact on the annealing towards the ground state. While many papers show interesting optimization results with a sizable number of qubits, a clear evidence of a full quantum coherent behavior during the whole annealing procedure is still lacking. In this paper we show that quantum non-demolition (weak) measurements of Leggett Garg inequalities can be used to efficiently assess the quantumness of the QA procedure. Numerical simulations based on a weak coupling Lindblad approach are compared with classical Langevin simulations to support our statements., 7 pages, 3 figures. Includes supplementary material file

It was recently shown that certain subsurface hydrological inverse problems—here framed as determining the composition of an aquifer from pressure readings—can be solved on a quantum annealer. However, the quantum annealer performance suffered when solving problems where the aquifer was composed of materials with vastly different permeability, which is often encountered in practice. In this paper, we study why this regime is difficult and use several pre- and post-processing tools to address these issues. This study has three benefits: it improves quantum annealing performance for real-world problems in hydrology, it studies the scaling behavior for these problems (which were previously studied at a fixed size), and it elucidates a challenging class of problems that are amenable to quantum annealers.

Sampling equilibrium ensembles of dense polymer mixtures is a paradigmatically hard problem in computational physics, even in lattice-based models. Here, we develop a formalism based on interacting binary tensors that allows for tackling this problem using quantum annealing machines. Our approach is general in that properties such as self-avoidance, branching, and looping can all be specified in terms of quadratic interactions of the tensors. Microstates realizations of different lattice polymer ensembles are then seamlessly generated by solving suitable discrete energy-minimization problems. This approach enables us to capitalize on the strengths of quantum annealing machines, as we demonstrate by sampling polymer mixtures from low to high densities, using the D-Wave quantum computer. Our systematic approach offers a promising avenue to harness the rapid development of quantum computers for sampling discrete models of filamentous soft-matter systems., Supplementary Material Included

We develop a protocol for continuous operation of a quantum error correcting code for protection of coherent evolution due to an encoded Hamiltonian against environmental errors, using the three qubit bit flip code and bit flip errors as a canonical example. To detect errors in real time, we filter the output signals from continuous measurement of the error syndrome operators and use a double thresholding protocol for error diagnosis, while correction of errors is done as in the conventional operation. We optimize our continuous operation protocol for evolution under quantum memory and under quantum annealing, by maximizing the fidelity between the target and actual logical states at a specified final time. In the case of quantum memory we show that our continuous operation protocol yields a logical error rate that is slightly larger than the one obtained from using the optimal Wonham filter for error diagnosis. The advantage of our protocol is that it can be simpler to implement. For quantum annealing, we show that our continuous quantum error correction protocol can significantly reduce the final logical state infidelity when the continuous measurements are sufficiently strong relative to the strength of the time-dependent Hamiltonian, and that it can also significantly reduces the run time relative to that of a classical encoding. These results suggest that a continuous implementation is suitable for quantum error correction in the presence of encoded time-dependent Hamiltonians, opening the possibility of many applications in quantum simulation and quantum annealing., 22 pages, 12 figures

We introduce a two-parameter approximate counter-diabatic term into the Hamiltonian of the transverse-field Ising model for quantum annealing to accelerate convergence to the solution, generalizing an existing single-parameter approach. The protocol is equivalent to unconventional diabatic control of the longitudinal and transverse fields in the transverse-field Ising model and thus makes it more feasible for experimental realization than an introduction of new terms such as non-stoquastic catalysts toward the same goal of performance enhancement. We test the idea for the $p$-spin model with $p=3$, which has a first-order quantum phase transition, and show that our two-parameter approach leads to significantly larger ground-state fidelity and lower residual energy than those by traditional quantum annealing as well as by the single-parameter method. We also find a scaling advantage in terms of the time to solution as a function of the system size in a certain range of parameters as compared to the traditional methods., 14 pages, 6 figures

Quantum annealers offer an efficient way to compute high quality solutions of NP-hard problems when expressed in a QUBO (quadratic unconstrained binary optimization) or an Ising form. This is done by mapping a problem onto the physical qubits and couplers of the quantum chip, from which a solution is read after a process called quantum annealing. However, this process is subject to multiple sources of biases, including poor calibration, leakage between adjacent qubits, control biases, etc., which might negatively influence the quality of the annealing results. In this work, we aim at mitigating the effect of such biases for solving constrained optimization problems, by offering a two-step method, and apply it to Graph Partitioning. In the first step, we measure and reduce any biases that result from implementing the constraints of the problem. In the second, we add the objective function to the resulting bias-corrected implementation of the constraints, and send the problem to the quantum annealer. We apply this concept to Graph Partitioning, an important NP-hard problem, which asks to find a partition of the vertices of a graph that is balanced (the constraint) and minimizes the cut size (the objective). We first quantify the bias of the implementation of the constraint on the quantum annealer, that is, we require, in an unbiased implementation, that any two vertices have the same likelihood of being assigned to the same or to different parts of the partition. We then propose an iterative method to correct any such biases. We demonstrate that, after adding the objective, solving the resulting bias-corrected Ising problem on the quantum annealer results in a higher solution accuracy.

Qilimanjaro Quantum Tech is the full-stack quantum spin-off of three research institutions, the Barcelona Supercomputing Center (BSC), the Institute for High Energy Physics (IFAE) and the University of Barcelona (UB). The company addresses the emerging quantum readiness demand from industry and academia, by providing both algorithmic development services as well as access to a new coherent quantum annealer platform, a special purpose quantum computer. Qilimanjaro is a member of the AVaQus European Commission’s H2020 FET-Open consortium for coherent quantum annealing development, which is led by one of Qilimanjaro’s founders at IFAE. A special feature of Qilimanjaro are its funding sources being exclusively international client contracts. Qilimanjaro is fully funded by client contracts. In addition it is a member of the H2020—FET-Open AVaQus grant agreement no. 899561 (November 2020).

Path integral quantum Monte Carlo (PIMC) is a method for estimating thermal equilibrium properties of stoquastic quantum spin systems by sampling from a classical Gibbs distribution using Markov chain Monte Carlo. The PIMC method has been widely used to study the physics of materials and for simulated quantum annealing, but these successful applications are rarely accompanied by formal proofs that the Markov chains underlying PIMC rapidly converge to the desired equilibrium distribution. In this work we analyze the mixing time of PIMC for 1D stoquastic Hamiltonians, including disordered transverse Ising models (TIM) with long-range algebraically decaying interactions as well as disordered XY spin chains with nearest-neighbor interactions. By bounding the convergence time to the equilibrium distribution we rigorously justify the use of PIMC to approximate partition functions and expectations of observables for these models at inverse temperatures that scale at most logarithmically with the number of qubits. The mixing time analysis is based on the canonical paths method applied to the single-site Metropolis Markov chain for the Gibbs distribution of 2D classical spin models with couplings related to the interactions in the quantum Hamiltonian. Since the system has strongly nonisotropic couplings that grow with system size, it does not fall into the known cases where 2D classical spin models are known to mix rapidly., 26 pages, 2 figures, version published in Quantum

Restricted Boltzmann Machines (RBMs) have been proposed for developing neural networks for a variety of unsupervised machine learning applications such as image recognition, drug discovery, and materials design. The Boltzmann probability distribution is used as a model to identify network parameters by optimizing the likelihood of predicting an output given hidden states trained on available data. Training such networks often requires sampling over a large probability space that must be approximated during gradient based optimization. Quantum annealing has been proposed as a means to search this space more efficiently which has been experimentally investigated on D-Wave hardware. D-Wave implementation requires selection of an effective inverse temperature or hyperparameter ($$\beta $$ β ) within the Boltzmann distribution which can strongly influence optimization. Here, we show how this parameter can be estimated as a hyperparameter applied to D-Wave hardware during neural network training by maximizing the likelihood or minimizing the Shannon entropy. We find both methods improve training RBMs based upon D-Wave hardware experimental validation on an image recognition problem. Neural network image reconstruction errors are evaluated using Bayesian uncertainty analysis which illustrate more than an order magnitude lower image reconstruction error using the maximum likelihood over manually optimizing the hyperparameter. The maximum likelihood method is also shown to out-perform minimizing the Shannon entropy for image reconstruction.

Physical Ising machines rely on nature to guide a dynamical system towards an optimal state which can be read out as a heuristical solution to a combinatorial optimization problem. Such designs that use nature as a computing mechanism can lead to higher performance and/or lower operation costs. Quantum annealers are a prominent example of such efforts. However, existing Ising machines are generally bulky and energy intensive. Such disadvantages may be acceptable if these designs provide some significant intrinsic advantages at a much larger scale in the future, which remains to be seen. But for now, integrated electronic designs of Ising machines allow more immediate applications. We propose one such design that uses bistable nodes, coupled with programmable and variable strengths. The design is fully CMOS compatible for on-chip applications and demonstrates competitive solution quality and significantly superior execution time and energy.

Quantum annealing algorithm is a classical natural computing method for skeuomorphs, and its algorithm design and application research have achieved fruitful results, so it is widely integrated into the research of modern intelligent optimization algorithm. This paper attempts to use the spiking neural network (SNN) dynamic system model to simulate the operation mechanism and convergence of the quantum annealing algorithm, and compares the process of searching the optimal solution to the elastic motion in the quantum tunneling field, and the change of function value during the operation of the algorithm is the simple harmonic vibration or damped vibration of quantum. Spiking neural network dynamic system model simulates the human brain by incorporating synaptic state and time components into their operational models, which represents the process of quantum fluctuations. The local convergence in the early stage and the global convergence in the late stage of the algorithm are proved by using the qualitative theory of ordinary differential equations to solve and analyze the dynamic system model, and a reasonable theoretical explanation is given for its operation mechanism. Several typical test problems are selected for experimental verification. The experimental results show that the numerical convergence curve is consistent with the convergence conclusion of theoretical analysis. Finally, both theoretical and experimental analyses show that the SNN dynamic system model established in this paper is suitable to describe the quantum annealing algorithm for optimization.

Adiabatic gauge potential is the origin of nonadiabatic transitions. In counterdiabatic driving, which is a method of shortcuts to adiabaticity, adiabatic gauge potential can be used to realize identical dynamics to adiabatic time evolution without requiring slow change of parameters. We introduce an algebraic expression of adiabatic gauge potential. Then, we find that the explicit form of adiabatic gauge potential can be easily determined by some algebraic calculations. We demonstrate this method by using a single-spin system, a two-spin system, and the transverse Ising chain. Moreover, we derive a lower bound for fidelity to adiabatic time evolution based on the quantum speed limit. This bound enables us to know the worst case performance of approximate adiabatic gauge potential. We can also use this bound to find dominant terms in adiabatic gauge potential to suppress nonadiabatic transitions. We apply this bound to magnetization reversal of the two-spin system and to quantum annealing of the transverse Ising chain. Adiabatic gauge potential reflects structure of energy eigenstates, and thus we also discuss detection of quantum phase transitions by using adiabatic gauge potential. We find a signature of a quantum phase transition in the transverse Ising chain.

There is a tremendous interest in developing practical applications for noisy intermediate-scale quantum processors without the overhead required by full error correction. Near-term quantum information processing is especially challenging within the standard gate model, as algorithms quickly lose fidelity as the problem size and circuit depth grow. This has lead to a number of non-gate-model approaches such as analog quantum simulation and quantum annealing. These come with specific hardware requirements that are different than that of a universal gate-based quantum computer. We have previously proposed an approach called the single-excitation subspace (SES) method, which uses a complete graph of superconducting qubits with tunable coupling. Without error correction the SES method is not scalable, but it offers several algorithmic components with constant depth, which is highly desirable for near-term use. The challenge of the SES method is that it requires a physical qubit for every basis state in the computer’s Hilbert space. This imposes exponentially large resource costs for algorithms using registers of ancillary qubits, as each ancilla would double the required graph size. Here we show how to circumvent this doubling by leaving the SES and fusing it with a multi-ancilla Hilbert space. Specifically, we implement the tensor product of an SES register holding “data” with one or more ancilla qubits, which are able to independently control arbitrary $$n\!\times \!n$$ n × n unitary operations on the data in a constant number of steps. This enables a hybrid form of quantum computation where fast SES operations are performed on the data, traditional logic gates and measurements are performed on the ancillas, and controlled-unitaries act between. As example applications, we give ancilla-assisted SES implementations of quantum phase estimation and the quantum linear system solver of Harrow, Hassidim, and Lloyd.

Quantum annealing is getting increasing attention in combinatorial optimization. The quantum processing unit by D-Wave is constructed to approximately solve Ising models on so-called Chimera graphs. Ising models are equivalent to quadratic unconstrained binary optimization (QUBO) problems and maximum cut problems on the associated graphs. We have tailored branch-and-cut as well as semidefinite programming algorithms for solving Ising models for Chimera graphs to provable optimality and use the strength of these approaches for comparing our solution values to those obtained on the current quantum annealing machine, D-Wave 2000Q. This allows for the assessment of the quality of solutions produced by the D-Wave hardware. In addition, we also evaluate the performance of a heuristic by Selby. It has been a matter of discussion in the literature how well the D-Wave hardware performs at its native task, and our experiments shed some more light on this issue. In particular, we examine how reliably the D-Wave computer can deliver true optimum solutions and present some surprising results.

The article addresses the possibility of implementing spin network states, used in the loop quantum gravity approach to Planck scale physics on an adiabatic quantum computer. The discussion focuses on applying currently available technologies and analyzes a concrete example of a D-Wave machine. It is introduced a class of simple spin network states which can be implemented on the Chimera graph architecture of the D-Wave quantum processor. However, extension beyond the currently available quantum processor topologies is required to simulate more sophisticated spin network states. This may inspire new generations of adiabatic quantum computers. A possibility of simulating loop quantum gravity is discussed, and a method of solving a graph non-changing scalar (Hamiltonian) constraint with the use of adiabatic quantum computations is proposed. The presented results establish a basis for the future simulations of Planck scale physics, specifically quantum cosmological configurations, on quantum annealers.

In this article, we present QuASeR, a reference-free DNA sequence reconstruction implementation via de novo assembly on both gate-based and quantum annealing platforms. Each one of the four steps of the implementation (TSP, QUBO, Hamiltonians and QAOA) is explained with simple proof-of-concept examples to target both the genomics research community and quantum application developers in a self-contained manner. The details of the implementation are discussed for the various layers of the quantum full-stack accelerator design. We also highlight the limitations of current classical simulation and available quantum hardware systems. The implementation is open-source and can be found on https://github.com/prince-ph0en1x/QuASeR., Comment: 24 pages

Quantum annealing was originally proposed as an approach for solving combinatorial optimisation problems using quantum effects. D-Wave Systems has released a production model of quantum annealing hardware. However, the inherent noise and various environmental factors in the hardware hamper the determination of optimal solutions. In addition, the freezing effect in regions with weak quantum fluctuations generates outputs approximately following a Gibbs--Boltzmann distribution at an extremely low temperature. Thus, a quantum annealer may also serve as a fast sampler for the Ising spin-glass problem, and several studies have investigated Boltzmann machine learning using a quantum annealer. Previous developments have focused on comparing the performance in the standard distance of the resulting distributions between conventional methods in classical computers and sampling by a quantum annealer. In this study, we focused on the performance of a quantum annealer as a generative model. To evaluate its performance, we prepared a discriminator given by a neural network trained on an a priori dataset. The evaluation results show a higher performance of quantum annealing compared with the classical approach for Boltzmann machine learning., Comment: 10 pages, 8 figures

Lattice gauge theory is an essential tool for strongly interacting non-Abelian fields, such as those in quantum chromodynamics where lattice results have been of central importance for several decades. Recent studies suggest that quantum computers could extend the reach of lattice gauge theory in dramatic ways, but the usefulness of quantum annealing hardware for lattice gauge theory has not yet been explored. In this work, we implement SU(2) pure gauge theory on a quantum annealer for lattices comprising a few plaquettes in a row with a periodic boundary condition. These plaquettes are in two spatial dimensions and calculations use the Hamiltonian formulation where time is not discretized. Numerical results are obtained from calculations on D-Wave Advantage hardware for eigenvalues, eigenvectors, vacuum expectation values, and time evolution. The success of this initial exploration indicates that the quantum annealer might become a useful hardware platform for some aspects of lattice gauge theories., Comment: 19 pages, 10 figures, updated to match the Physical Review D version

The promise of quantum computing to open new unexplored possibilities in several scientific fields has been long discussed, but until recently the lack of a functional quantum computer has confined this discussion mostly to theoretical algorithmic papers. It was only in the last few years that small but functional quantum computers have become available to the broader research community. One paradigm in particular, quantum annealing, can be used to sample optimal solutions for a number of NP-hard optimization problems represented with classical operations research tools, providing an easy access to the potential of this emerging technology. One of the tasks that most naturally fits in this mathematical formulation is feature selection. In this paper, we investigate how to design a hybrid feature selection algorithm for recommender systems that leverages the domain knowledge and behavior hidden in the user interactions data. We represent the feature selection as an optimization problem and solve it on a real quantum computer, provided by D-Wave. The results indicate that the proposed approach is effective in selecting a limited set of important features and that quantum computers are becoming powerful enough to enter the wider realm of applied science.

We benchmark the 5000+ qubit system Advantage coupled with the Hybrid Solver Service 2 released by D-Wave Systems Inc. in September 2020 by using a new class of optimization problems called garden optimization problems known in companion planting. These problems are scalable to an arbitrarily large number of variables and intuitively find application in real-world scenarios. We derive their QUBO formulation and illustrate their relation to the quadratic assignment problem. We demonstrate that the Advantage system and the new hybrid solver can solve larger problems in less time than their predecessors. However, we also show that the solvers based on the 2000+ qubit system DW2000Q sometimes produce more favourable results if they can solve the problems., open-source code available at https://jugit.fz-juelich.de/qip/garden-optimization-problem.git

In order to treat all-to-all-connected quadratic binary optimization problems (QUBOs) with hard- ware quantum annealers, an embedding of the original problem is required due to the sparsity of the topology of the hardware. The embedding of fully connected graphs-typically found in industrial applications incurs a quadratic space overhead and thus a significant overhead in the time to solution. Here, we investigate this embedding penalty of established planar embedding schemes such as square-lattice embedding, embedding on a chimera lattice, and the Lechner-Hauke-Zoller scheme, using simulated quantum annealing on classical hardware. Large-scale quantum Monte Carlo simulation suggests a polynomial time-to-solution overhead. Our results demonstrate that standard analog quantum annealing hardware is at a disadvantage in comparison to classical digital annealers, as well as gate-model quantum annealers, and could also serve as a benchmark for improvements of the standard quantum annealing protocol., PRX Quantum, 2 (4), ISSN:2691-3399

Optimal parameter setting for applications problems embedded into hardware graphs is key to practical quantum annealers (QA). Embedding chains typically crop up as harmful Griffiths phases, but can be used as a resource as we show here: to balance out singularities in the logical problem changing its universality class. Smart choice of embedding parameters reduces annealing times for random Ising chain from $O(exp[c\sqrt N])$ to $O(N^2)$. Dramatic reduction in time-to-solution for QA is confirmed by numerics, for which we developed a custom integrator to overcome convergence issues., 11 pages [5 pages (3 figs) main text+references; 5 pages (2 figs) appendix; 1 page code listing]

Recent work has shown that quantum annealing for machine learning, referred to as QAML, can perform comparably to state-of-the-art machine learning methods with a specific application to Higgs boson classification. We propose QAML-Z, an algorithm that iteratively zooms in on a region of the energy surface by mapping the problem to a continuous space and sequentially applying quantum annealing to an augmented set of weak classifiers. Results on a programmable quantum annealer show that QAML-Z matches classical deep neural network performance at small training set sizes and reduces the performance margin between QAML and classical deep neural networks by almost 50% at large training set sizes, as measured by area under the receiver operating characteristic curve. The significant improvement of quantum annealing algorithms for machine learning and the use of a discrete quantum algorithm on a continuous optimization problem both opens a class of problems that can be solved by quantum annealers and suggests the approach in performance of near-term quantum machine learning towards classical benchmarks.

We show that the quantum approximate optimization algorithm (QAOA) can construct, with polynomially scaling resources, the ground state of the fully connected $p$-spin Ising ferromagnet, a problem that notoriously poses severe difficulties to a vanilla quantum annealing (QA) approach due to the exponentially small gaps encountered at first-order phase transition for $p\ensuremath{\ge}3$. For a target ground state at arbitrary transverse field, we find that an appropriate QAOA parameter initialization is necessary to achieve good performance of the algorithm when the number of variational parameters $2P$ is much smaller than the system size $N$ because of the large number of suboptimal local minima. Instead, when $P$ exceeds a critical value ${P}_{N}^{*}\ensuremath{\propto}N$, the structure of the parameter space simplifies, as all minima become degenerate. This allows achieving the ground state with perfect fidelity with a number of parameters scaling extensively with $N$ and with resources scaling polynomially with $N$.

The annealing schedule is optimized for a parameter in the Lechner-Hauke-Zoller (LHZ) scheme for quantum annealing designed for the all-to-all-interacting Ising model representing generic combinatorial optimization problems. We adapt the variational approach proposed by Matsuura et al. (arXiv:2003.09913) to the annealing schedule of a term representing a constraint for variables intrinsic to the LHZ scheme with the annealing schedule of other terms kept intact. Numerical results for a simple ferromagnetic model and the spin-glass problem show that nonmonotonic annealing schedules optimize the performance measured by the residual energy and the final ground-state fidelity. This improvement does not accompany a notable increase in the instantaneous energy gap, which suggests the importance of a dynamical viewpoint in addition to static analyses in the study of practically relevant diabatic processes in quantum annealing., 6 pages, 6 figures

In many real-life situations in engineering (and in other disciplines), we need to solve an optimization problem: we want an optimal design, we want an optimal control, etc. One of the main problems in optimization is avoiding local maxima (or minima). One of the techniques that helps with solving this problem is annealing: whenever we find ourselves in a possibly local maximum, we jump out with some probability and continue search for the true optimum. A natural way to organize such a probabilistic perturbation of the deterministic optimization is to use quantum effects. It turns out that often, quantum annealing works much better than non-quantum one. Quantum annealing is the main technique behind the only commercially available computational devices that use quantum effects-D-Wave computers. The efficiency of quantum annealing depends on the proper selection of the annealing schedule, i.e., schedule that describes how the perturbations decrease with time. Empirically, it has been found that two schedules work best: power law and exponential ones. In this paper, we provide a theoretical explanation for these empirical successes, by proving that these two schedules are indeed optimal (in some reasonable sense).

Platforms of Rydberg atoms have been proposed as promising candidates to solve some combinatorial optimization problems. Here we compute quantitative requirements on the system sizes and noise levels that these platforms must fulfill to reach quantum advantage in approximately solving the Unit-Disk Maximum Independent Set problem. Using noisy simulations of Rydberg platforms of up to 26 atoms interacting through realistic van der Waals interactions, we compute the average approximation ratio that can be attained with a simple quantum annealing-based heuristic within a fixed temporal computational budget. Based on estimates of the correlation lengths measured in the engineered quantum state, we extrapolate the results to large atom numbers and compare them to a simple classical approximation heuristic. We find that approximation ratios of at least $\ensuremath{\approx}0.84$ are within reach for near-future noise levels. Not taking into account further classical and quantum algorithmic improvements, we estimate that quantum advantage could be reached by attaining a number of controlled atoms of $\ensuremath{\sim}8000$ for a time budget of 2 s, and $\ensuremath{\sim}1000--1200$ for a time budget of 0.2 s, provided the coherence levels of the system can be improved by a factor 10 while maintaining a constant repetition rate.

With unprecedented increases in traffic load in today's wireless networks, design challenges shift from the wireless network itself to the computational support behind the wireless network. In this vein, there is new interest in quantum-compute approaches because of their potential to substantially speed up processing, and so improve network throughput. However, quantum hardware that actually exists today is much more susceptible to computational errors than silicon-based hardware, due to the physical phenomena of decoherence and noise. This paper explores the boundary between the two types of computation---classical-quantum hybrid processing for optimization problems in wireless systems---envisioning how wireless can simultaneously leverage the benefit of both approaches. We explore the feasibility of a hybrid system with a real hardware prototype using one of the most advanced experimentally available techniques today, reverse quantum annealing. Preliminary results on a low-latency, large MIMO system envisioned in the 5G New Radio roadmap are encouraging, showing approximately 2--10X better performance in terms of processing time than prior published results., Comment: HotNets 2020: Nineteenth ACM Workshop on Hot Topics in Networks (https://doi.org/10.1145/3422604.3425924)

Recently, a clustering method using a combinatorial optimization problem, called combinatorial clustering, has been drawing attention due to the rapid spreads of quantum annealing and simulated annealing. Combinatorial clustering is performed by minimizing an objective function under a condition to satisfy a constraint. The objective function and the constraint function are generally formulated to a unified objective function of a QUBO (Quadratic Unconstrained Binary Optimization) problem by the method of the Lagrange multiplier.Although the Lagrange multiplier needs to be large enough to avoid violating the one-hot constraint, the Lagrange multiplier usually cannot be set appropriately due to the limitation of the bit precision. The latest quantum annealer can handle values represented by only six or fewer bits. Even conventional computing systems cannot handle the larger value of the Lagrange multiplier as the number of data points increases.To solve this problem, this paper proposes combinatorial clustering that overcomes the limitations of the method of the Lagrange multiplier. The proposed method uses a QUBO solver that can externally define the one-hot constraint independent from the objective function, and the externally-defined constraint is satisfied by the bit-flip operations. Since the constraint function is not included in the objective function, it is no longer needed to determine the Lagrange multiplier. The experimental results show that the proposed method can improve the quality of clustering results.

We present a thorough investigation of problems that can be solved exactly with the level-1 quantum approximate optimization algorithm (QAOA). To this end, we implicitly define a class of problem Hamiltonians that are employed as phase separators in a level-1 QAOA circuit and provide unit overlap with a target subspace spanned by a set of computational basis states. For one-dimensional target subspaces, we identify instances within the implicitly defined class of Hamiltonians for which quantum annealing (QA) and simulated annealing (SA) have an exponentially small probability of finding the solution. Consequently, our results define a demarcation line between QAOA on one hand and QA and SA on the other, and highlight the fundamental differences between an interference-based search heuristic such as QAOA and heuristics that are based on thermal and quantum fluctuations like SA and QA respectively. Moreover, for two-dimensional solution subspaces, we are able to show that the depth of the QAOA circuit grows linearly with the Hamming distance between the two target states. We further show that there are no genuine solutions for target subspaces of dimension higher than 2 and smaller than ${2}^{n}$. We also transfer these results to instantaneous quantum polynomial (IQP) circuits.

Boltzmann machines have useful roles in deep learning applications, such as generative data modeling, initializing weights for other types of networks, or extracting efficient representations from high-dimensional data. Most Boltzmann machines use restricted topologies that exclude looping connectivity, as such connectivity creates complex distributions that are difficult to sample. We have used an open-system quantum annealer to sample from complex distributions and implement Boltzmann machines with looping connectivity. Further, we have created policies mapping Boltzmann machine variables to the quantum bits of an annealer. These policies, based on correlation and entropy metrics, dynamically reconfigure the topology of Boltzmann machines during training and improve performance.