Search

We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for combinatorial optimization problems. Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps that recursively simplify the problem. These reduction steps address the limitations of the quantum component and ensure solution feasibility in constrained optimization problems. Additionally, we use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware. We demonstrate the capabilities of our approach by informing QIRO with correlations from classical simulations of shallow (depth $p=1$) circuits of the quantum approximate optimization algorithm (QAOA), solving instances of maximum independent set and maximum satisfiability problems with hundreds of variables. We also demonstrate how QIRO can be deployed on a neutral atom quantum processor available online on Amazon Braket to find large independent sets of graphs. In summary, our scheme achieves results comparable to classical heuristics, such as simulated annealing and greedy algorithms, even with relatively weak quantum resources. Furthermore, enhancing the quality of these quantum resources improves the performance of the algorithms, highlighting the potential of QIRO. Notably, the modular nature of QIRO offers various avenues for modifications, positioning our work as a blueprint for designing a broader class of hybrid quantum-classical algorithms for combinatorial optimization., Comment: 17 pages, 10 figures. Revised Figs. 1 and 2. Accepted version

Rydberg atom arrays are among the leading contenders for the demonstration of quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi et al., Science 376, 1209 (2022)] we study the maximum independent set problem on unit-disk graphs with a broader range of classical solvers beyond the scope of the original paper. We carry out extensive numerical studies and assess problem hardness, using both exact and heuristic algorithms. We find that quasi-planar instances with Union-Jack-like connectivity can be solved to optimality for up to thousands of nodes within minutes, with both custom and generic commercial solvers on commodity hardware, without any instance-specific fine-tuning. We also perform a scaling analysis, showing that by relaxing the constraints on the classical simulated annealing algorithms considered in Ebadi et al., our implementation is competitive with the quantum algorithms. Conversely, instances with larger connectivity or less structure are shown to display a time-to-solution potentially orders of magnitudes larger. Based on these results we propose protocols to systematically tune problem hardness, motivating experiments with Rydberg atom arrays on instances orders of magnitude harder (for established classical solvers) than previously studied., Comment: Manuscript: 9 pages, 9 figures. Appendix: 2 pages, 4 figures

We propose and implement an interpretable machine learning classification model for Explainable AI (XAI) based on expressive Boolean formulas. Potential applications include credit scoring and diagnosis of medical conditions. The Boolean formula defines a rule with tunable complexity (or interpretability), according to which input data are classified. Such a formula can include any operator that can be applied to one or more Boolean variables, thus providing higher expressivity compared to more rigid rule-based and tree-based approaches. The classifier is trained using native local optimization techniques, efficiently searching the space of feasible formulas. Shallow rules can be determined by fast Integer Linear Programming (ILP) or Quadratic Unconstrained Binary Optimization (QUBO) solvers, potentially powered by special purpose hardware or quantum devices. We combine the expressivity and efficiency of the native local optimizer with the fast operation of these devices by executing non-local moves that optimize over subtrees of the full Boolean formula. We provide extensive numerical benchmarking results featuring several baselines on well-known public datasets. Based on the results, we find that the native local rule classifier is generally competitive with the other classifiers. The addition of non-local moves achieves similar results with fewer iterations, and therefore using specialized or quantum hardware could lead to a speedup by fast proposal of non-local moves., Comment: 28 pages, 16 figures, 4 tables

We propose and analyze the use of Bayesian optimization techniques to design quantum annealing schedules with minimal user and resource requirements. We showcase our scheme with results for two paradigmatic spin models. We find that Bayesian optimization is able to identify schedules resulting in fidelities several orders of magnitude better than standard protocols for both quantum and reverse annealing, as applied to the $p$-spin model. We also show that our scheme can help improve the design of hybrid quantum algorithms for hard combinatorial optimization problems, such as the maximum independent set problem, and illustrate these results via experiments on a neutral atom quantum processor available on Amazon Braket., Comment: 20 pages, 15 figures

We provide a comprehensive reply to the comment written by Stefan Boettcher [arXiv:2210.00623] and argue that the comment singles out one particular non-representative example problem, entirely focusing on the maximum cut problem (MaxCut) on sparse graphs, for which greedy algorithms are expected to perform well. Conversely, we highlight the broader algorithmic development underlying our original work, and (within our original framework) provide additional numerical results showing sizable improvements over our original data, thereby refuting the comment's original performance statements. Furthermore, it has already been shown that physics-inspired graph neural networks (PI-GNNs) can outperform greedy algorithms, in particular on hard, dense instances. We also argue that the internal (parallel) anatomy of graph neural networks is very different from the (sequential) nature of greedy algorithms, and (based on their usage at the scale of real-world social networks) point out that graph neural networks have demonstrated their potential for superior scalability compared to existing heuristics such as extremal optimization. Finally, we conclude highlighting the conceptual novelty of our work and outline some potential extensions., Comment: Manuscript: 2 pages, 1 figure. arXiv admin note: substantial text overlap with arXiv:2302.03602

We provide a comprehensive reply to the comment written by Chiara Angelini and Federico Ricci-Tersenghi [arXiv:2206.13211] and argue that the comment singles out one particular non-representative example problem, entirely focusing on the maximum independent set (MIS) on sparse graphs, for which greedy algorithms are expected to perform well. Conversely, we highlight the broader algorithmic development underlying our original work, and (within our original framework) provide additional numerical results showing sizable improvements over our original results, thereby refuting the comment's performance statements. We also provide results showing run-time scaling superior to the results provided by Angelini and Ricci-Tersenghi. Furthermore, we show that the proposed set of random d-regular graphs does not provide a universal set of benchmark instances, nor do greedy heuristics provide a universal algorithmic baseline. Finally, we argue that the internal (parallel) anatomy of graph neural networks is very different from the (sequential) nature of greedy algorithms and emphasize that graph neural networks have demonstrated their potential for superior scalability compared to existing heuristics such as parallel tempering. We conclude by discussing the conceptual novelty of our work and outline some potential extensions., Comment: Manuscript: 3 pages, 2 figures

We study quantum interior point methods (QIPMs) for second-order cone programming (SOCP), guided by the example use case of portfolio optimization (PO). We provide a complete quantum circuit-level description of the algorithm from problem input to problem output, making several improvements to the implementation of the QIPM. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm, including constant factors. The resource counts we find depend on instance-specific parameters, such as the condition number of certain linear systems within the problem. To determine the size of these parameters, we perform numerical simulations of small PO instances, which lead to concrete resource estimates for the PO use case. Our numerical results do not probe large enough instance sizes to make conclusive statements about the asymptotic scaling of the algorithm. However, already at small instance sizes, our analysis suggests that, due primarily to large constant pre-factors, poorly conditioned linear systems, and a fundamental reliance on costly quantum state tomography, fundamental improvements to the QIPM are required for it to lead to practical quantum advantage., Comment: 40 pages, 15 figures. v2: minor corrections and updates to match journal version

We solve robot trajectory planning problems at industry-relevant scales. Our end-to-end solution integrates highly versatile random-key algorithms with model stacking and ensemble techniques, as well as path relinking for solution refinement. The core optimization module consists of a biased random-key genetic algorithm. Through a distinct separation of problem-independent and problem-dependent modules, we achieve an efficient problem representation, with a native encoding of constraints. We show that generalizations to alternative algorithmic paradigms such as simulated annealing are straightforward. We provide numerical benchmark results for industry-scale data sets. Our approach is found to consistently outperform greedy baseline results. To assess the capabilities of today's quantum hardware, we complement the classical approach with results obtained on quantum annealing hardware, using qbsolv on Amazon Braket. Finally, we show how the latter can be integrated into our larger pipeline, providing a quantum-ready hybrid solution to the problem., Comment: 17 pages, 6 figures

We show how graph neural networks can be used to solve the canonical graph coloring problem. We frame graph coloring as a multi-class node classification problem and utilize an unsupervised training strategy based on the statistical physics Potts model. Generalizations to other multi-class problems such as community detection, data clustering, and the minimum clique cover problem are straightforward. We provide numerical benchmark results and illustrate our approach with an end-to-end application for a real-world scheduling use case within a comprehensive encode-process-decode framework. Our optimization approach performs on par or outperforms existing solvers, with the ability to scale to problems with millions of variables., Comment: Manuscript: 8 pages, 5 figures, 2 tables. Supplemental Material: 1 page, 2 tables

Combinatorial optimization problems are pervasive across science and industry. Modern deep learning tools are poised to solve these problems at unprecedented scales, but a unifying framework that incorporates insights from statistical physics is still outstanding. Here we demonstrate how graph neural networks can be used to solve combinatorial optimization problems. Our approach is broadly applicable to canonical NP-hard problems in the form of quadratic unconstrained binary optimization problems, such as maximum cut, minimum vertex cover, maximum independent set, as well as Ising spin glasses and higher-order generalizations thereof in the form of polynomial unconstrained binary optimization problems. We apply a relaxation strategy to the problem Hamiltonian to generate a differentiable loss function with which we train the graph neural network and apply a simple projection to integer variables once the unsupervised training process has completed. We showcase our approach with numerical results for the canonical maximum cut and maximum independent set problems. We find that the graph neural network optimizer performs on par or outperforms existing solvers, with the ability to scale beyond the state of the art to problems with millions of variables., Comment: Manuscript: 13 pages, 5 figures, 1 table. Supplemental Material: 1 page, 1 table

We propose a protocol for the deterministic generation of entanglement between two ensembles of nuclear spins surrounding two distant quantum dots. The protocol relies on the injection of electrons with definite polarization in each quantum dot and the coherent transfer of electrons from one quantum dot to the other. Computing the exact dynamics for small systems, and using an effective master equation and approximate non-linear equations of motion for larger systems, we are able to confirm that our protocol indeed produces entanglement for both homogeneous and inhomogeneous systems. Last, we analyze the feasibility of our protocol in several current experimental platforms.

Localized electronic and nuclear spin qubits in the solid state constitute a promising platform for storage and manipulation of quantum information, even at room temperature. However, the development of scalable systems requires the ability to entangle distant spins, which remains a challenge today. We propose and analyze an efficient, heralded scheme that employs a parity measurement in a decoherence free subspace to enable fast and robust entanglement generation between distant spin qubits mediated by a hot mechanical oscillator. We find that high-fidelity entanglement at cryogenic and even ambient temperatures is feasible with realistic parameters, and show that the entangled pair can be subsequently leveraged for deterministic controlled-NOT operations between nuclear spins. Our results open the door for novel quantum processing architectures for a wide variety of solid-state spin qubits.

Wigner crystals are prime candidates for the realization of regular electron lattices under minimal requirements on external control and electronics. However, several technical challenges have prevented their detailed experimental investigation and applications to date. We propose an implementation of two-dimensional electron lattices for quantum simulation of Ising spin systems based on self-assembled Wigner crystals in transition-metal dichalcogenides. We show that these semiconductors allow for minimally invasive all-optical detection schemes of charge ordering and total spin. For incident light with optimally chosen beam parameters and polarization, we predict a strong dependence of the transmitted and reflected signals on the underlying lattice periodicity, thus revealing the charge order inherent in Wigner crystals. At the same time, the selection rules in transition-metal dichalcogenides provide direct access to the spin degree of freedom via Faraday rotation measurements., Comment: 15 pages, 12 figures

We demonstrate a new mechanical transduction platform for individual spin qubits. In our approach, single micro-magnets are trapped using a type-II superconductor in proximity of spin qubits, enabling direct magnetic coupling between the two systems. Controlling the distance between the magnet and the superconductor during cooldown, we demonstrate three dimensional trapping with quality factors around one million and kHz trapping frequencies. We further exploit the large magnetic moment to mass ratio of this mechanical oscillator to couple its motion to the spin degree of freedom of an individual nitrogen vacancy center in diamond. Our approach provides a new path towards interfacing individual spin qubits with mechanical motion for testing quantum mechanics with mesoscopic objects, realization of quantum networks, and ultra-sensitive metrology., Comment: 5 pages, 4 figures

We propose and analyze a setup based on (solid-state) qubits coupled to a common multi-mode transmission line, which allows for coherent spin-spin interactions over macroscopic on-chip distances, without any ground-state cooling requirements for the data bus. Our approach allows for the realization of fast deterministic quantum gates between distant qubits, the simulation of quantum spin models with engineered (long-range) interactions, and provides a flexible architecture for the implementation of quantum approximate optimization algorithms., Comment: Manuscript: 5 pages, 4 figures. Supplementary Material: 14 pages, 5 figures

We propose and analyze magnetic traps and lattices for electrons in semiconductors. We provide a general theoretical framework and show that thermally stable traps can be generated by magnetically driving the particle's internal spin transition, akin to optical dipole traps for ultra-cold atoms. Next we discuss in detail periodic arrays of magnetic traps, i.e. magnetic lattices, as a platform for quantum simulation of exotic Hubbard models, with lattice parameters that can be tuned in real time. Our scheme can be readily implemented in state-of-the-art experiments, as we particularize for two specific setups, one based on a superconducting circuit and another one based on surface acoustic waves., Comment: 18 pages, 8 figures

We propose and analyze a solid-state platform based on surface acoustic waves (SAWs) for trapping, cooling and controlling (charged) particles, as well as the simulation of quantum many-body systems. We develop a general theoretical framework demonstrating the emergence of effective time-independent acoustic trapping potentials for particles in two- or one-dimensional structures. As our main example we discuss in detail the generation and applications of a stationary, but movable acoustic pseudo-lattice (AL) with lattice parameters that are reconfigurable in situ. We identify the relevant figures of merit, discuss potential experimental platforms for a faithful implementation of such an acoustic lattice, and provide estimates for typical system parameters. With a projected lattice spacing on the scale of 100nm, this approach allows for relatively large energy scales in the realization of fermionic Hubbard models, with the ultimate prospect of entering the low temperature, strong interaction regime. Experimental imperfections as well as read-out schemes are discussed., Comment: Manuscript: 10.5 pages, 5 figures, 1 table. Appendices: 8 pages, 1 table. v2: version as published, Journal-Ref added

We propose and analyze a high-fidelity hot gate for generic spin-resonator systems which allows for coherent spin-spin coupling, in the presence of a thermally populated resonator mode. Our scheme is non-perturbative, applies to a broad class of physical systems, including for example spins coupled to circuit-QED and surface acoustic wave resonators as well as nanomechanical oscillators, and can be implemented readily with state-of-the-art experimental setups. We provide and numerically verify simple expressions for the fidelity of creating maximally entangled states under realistic conditions., Comment: Manuscript: 5 pages, 4 figures. Appendices: 23 pages, 16 figures. v2: version as published, Journal-Ref added

We propose a scheme for deterministic generation and long-term stabilization of entanglement between two electronic spin qubits confined in spatially separated quantum dots. Our approach relies on an electronic quantum bus, consisting either of quantum Hall edge channels or surface acoustic waves, that can mediate long-range coupling between localized spins over distances of tens of micrometers. Since the entanglement is actively stabilized by dissipative dynamics, our scheme is inherently robust against noise and imperfections., Comment: Updated version. 19 pages, 19 figures

We propose a universal, on-chip quantum transducer based on surface acoustic waves in piezo-active materials. Because of the intrinsic piezoelectric (and/or magnetostrictive) properties of the material, our approach provides a universal platform capable of coherently linking a broad array of qubits, including quantum dots, trapped ions, nitrogen-vacancy centers or superconducting qubits. The quantized modes of surface acoustic waves lie in the gigahertz range, can be strongly confined close to the surface in phononic cavities and guided in acoustic waveguides. We show that this type of surface acoustic excitations can be utilized efficiently as a quantum bus, serving as an on-chip, mechanical cavity-QED equivalent of microwave photons and enabling long-range coupling of a wide range of qubits., Comment: Manuscript: 8 pages, 3 figures. Appendices: 17 pages, 12 figures. v2: version as published, Journal-Ref added

We theoretically study the nuclear spin dynamics driven by electron transport and hyperfine interaction in an electrically-defined double quantum dot (DQD) in the Pauli-blockade regime. We derive a master-equation-based framework and show that the coupled electron-nuclear system displays an instability towards the buildup of large nuclear spin polarization gradients in the two quantum dots. In the presence of such inhomogeneous magnetic fields, a quantum interference effect in the collective hyperfine coupling results in sizable nuclear spin entanglement between the two quantum dots in the steady state of the evolution. We investigate this effect using analytical and numerical techniques, and demonstrate its robustness under various types of imperfections., Comment: 35 pages, 19 figures. This article provides the full analysis of a scheme proposed in Phys. Rev. Lett. 111, 246802 (2013). v2: version as published

We propose a scheme for the deterministic generation of steady-state entanglement between the two nuclear spin ensembles in an electrically defined double quantum dot. Due to quantum interference in the collective coupling to the electronic degrees of freedom, the nuclear system is actively driven into a two-mode squeezed-like target state. The entanglement build-up is accompanied by a self-polarization of the nuclear spins towards large Overhauser field gradients. Moreover, the feedback between the electronic and nuclear dynamics leads to multi-stability and criticality in the steady-state solutions., Comment: Manuscript: 5 pages, 3 figures. Supplementary Information: 4 pages, 2 figures. v2: accepted version, Journal-Ref added

We theoretically show that intriguing features of coherent many-body physics can be observed in electron transport through a quantum dot (QD). We first derive a master equation based framework for electron transport in the Coulomb-blockade regime which includes hyperfine (HF) interaction with the nuclear spin ensemble in the QD. This general tool is then used to study the leakage current through a single QD in a transport setting. We find that, for an initially polarized nuclear system, the proposed setup leads to a strong current peak, in close analogy with superradiant emission of photons from atomic ensembles. This effect could be observed with realistic experimental parameters and would provide clear evidence of coherent HF dynamics of nuclear spin ensembles in QDs., Comment: 21 pages, 10 figures

Laser-induced optical potentials for atoms have led to remarkable advances in precision measurement, quantum information, and towards addressing fundamental questions in condensed matter physics. Here, we describe analogous optical potentials for electrons in quantum wells and wires that can be generated by optically driving the transition between a single electron and a three-body electron-exciton bound state, known as a trion. The existence of a bound trion state adds a term to the ac Stark shift of the material proportional to the light intensity at the position of the electron. According to our theoretical calculations, this shift can be large relative to the thermal equilibrium temperature of the electron, resulting in a relatively strong optical potential that could be used to trap, guide, and manipulate individual electrons within a semiconductor quantum well or wire. These potentials can be thought of as artificial nano-structures on the scale of 100 nm that can be spin-dependent and reconfigurable in real-time. Our results suggest the possibility of integrating ultrafast optics and gate voltages in new resolved-carrier semiconductor opto-electronic devices, with potential applications in fields such as nano-electronics, spintronics, and quantum information processing, Comment: Article and Supplemental Materials; This is a preprint of the original submission to Nature Physics