-
Combinatorial Reasoning: Selecting Reasons in Generative AI Pipelines via Combinatorial Optimization
Authors:
Mert Esencan,
Tarun Advaith Kumar,
Ata Akbari Asanjan,
P. Aaron Lott,
Masoud Mohseni,
Can Unlu,
Davide Venturelli,
Alan Ho
Abstract:
Recent Large Language Models (LLMs) have demonstrated impressive capabilities at tasks that require human intelligence and are a significant step towards human-like artificial intelligence (AI). Yet the performance of LLMs at reasoning tasks have been subpar and the reasoning capability of LLMs is a matter of significant debate. While it has been shown that the choice of the prompting technique to…
▽ More
Recent Large Language Models (LLMs) have demonstrated impressive capabilities at tasks that require human intelligence and are a significant step towards human-like artificial intelligence (AI). Yet the performance of LLMs at reasoning tasks have been subpar and the reasoning capability of LLMs is a matter of significant debate. While it has been shown that the choice of the prompting technique to the LLM can alter its performance on a multitude of tasks, including reasoning, the best performing techniques require human-made prompts with the knowledge of the tasks at hand. We introduce a framework for what we call Combinatorial Reasoning (CR), a fully-automated prompting method, where reasons are sampled from an LLM pipeline and mapped into a Quadratic Unconstrained Binary Optimization (QUBO) problem. The framework investigates whether QUBO solutions can be profitably used to select a useful subset of the reasons to construct a Chain-of-Thought style prompt. We explore the acceleration of CR with specialized solvers. We also investigate the performance of simpler zero-shot strategies such as linear majority rule or random selection of reasons. Our preliminary study indicates that coupling a combinatorial solver to generative AI pipelines is an interesting avenue for AI reasoning and elucidates design principles for future CR methods.
△ Less
Submitted 19 June, 2024;
originally announced July 2024.
-
X-ResQ: Reverse Annealing for Quantum MIMO Detection with Flexible Parallelism
Authors:
Minsung Kim,
Abhishek Kumar Singh,
Davide Venturelli,
John Kaewell,
Kyle Jamieson
Abstract:
Quantum Annealing (QA)-accelerated MIMO detection is an emerging research approach in the context of NextG wireless networks. The opportunity is to enable large MIMO systems and thus improve wireless performance. The approach aims to leverage QA to expedite the computation required for theoretically optimal but computationally-demanding Maximum Likelihood detection to overcome the limitations of t…
▽ More
Quantum Annealing (QA)-accelerated MIMO detection is an emerging research approach in the context of NextG wireless networks. The opportunity is to enable large MIMO systems and thus improve wireless performance. The approach aims to leverage QA to expedite the computation required for theoretically optimal but computationally-demanding Maximum Likelihood detection to overcome the limitations of the currently deployed linear detectors. This paper presents X-ResQ, a QA-based MIMO detector system featuring fine-grained quantum task parallelism that is uniquely enabled by the Reverse Annealing (RA) protocol. Unlike prior designs, X-ResQ has many desirable system properties for a parallel QA detector and has effectively improved detection performance as more qubits are assigned. In our evaluations on a state-of-the-art quantum annealer, fully parallel X-ResQ achieves near-optimal throughput (over 10 bits/s/Hz) for $4\times6$ MIMO with 16-QAM using six levels of parallelism with 240 qubits and $220~μ$s QA compute time, achieving 2.5--5$\times$ gains compared against other tested detectors. For more comprehensive evaluations, we implement and evaluate X-ResQ in the non-quantum digital setting. This non-quantum X-ResQ demonstration showcases the potential to realize ultra-large $1024\times1024$ MIMO, significantly outperforming other MIMO detectors, including the state-of-the-art RA detector classically implemented in the same way.
△ Less
Submitted 9 March, 2024; v1 submitted 28 February, 2024;
originally announced February 2024.
-
Benchmarking the Operation of Quantum Heuristics and Ising Machines: Scoring Parameter Setting Strategies on Optimization Applications
Authors:
David E. Bernal Neira,
Robin Brown,
Pratik Sathe,
Filip Wudarski,
Marco Pavone,
Eleanor G. Rieffel,
Davide Venturelli
Abstract:
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 st…
▽ More
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.
△ Less
Submitted 15 February, 2024;
originally announced February 2024.
-
Accelerating Continuous Variable Coherent Ising Machines via Momentum
Authors:
Robin Brown,
Davide Venturelli,
Marco Pavone,
David E. Bernal Neira
Abstract:
The Coherent Ising Machine (CIM) is a non-conventional architecture that takes inspiration from physical annealing processes to solve Ising problems heuristically. Its dynamics are naturally continuous and described by a set of ordinary differential equations that have been proven to be useful for the optimization of continuous variables non-convex quadratic optimization problems. The dynamics of…
▽ More
The Coherent Ising Machine (CIM) is a non-conventional architecture that takes inspiration from physical annealing processes to solve Ising problems heuristically. Its dynamics are naturally continuous and described by a set of ordinary differential equations that have been proven to be useful for the optimization of continuous variables non-convex quadratic optimization problems. The dynamics of such Continuous Variable CIMs (CV-CIM) encourage optimization via optical pulses whose amplitudes are determined by the negative gradient of the objective; however, standard gradient descent is known to be trapped by local minima and hampered by poor problem conditioning. In this work, we propose to modify the CV-CIM dynamics using more sophisticated pulse injections based on tried-and-true optimization techniques such as momentum and Adam. Through numerical experiments, we show that the momentum and Adam updates can significantly speed up the CV-CIM's convergence and improve sample diversity over the original CV-CIM dynamics. We also find that the Adam-CV-CIM's performance is more stable as a function of feedback strength, especially on poorly conditioned instances, resulting in an algorithm that is more robust, reliable, and easily tunable. More broadly, we identify the CIM dynamical framework as a fertile opportunity for exploring the intersection of classical optimization and modern analog computing.
△ Less
Submitted 22 January, 2024;
originally announced January 2024.
-
Design and execution of quantum circuits using tens of superconducting qubits and thousands of gates for dense Ising optimization problems
Authors:
Filip B. Maciejewski,
Stuart Hadfield,
Benjamin Hall,
Mark Hodson,
Maxime Dupont,
Bram Evert,
James Sud,
M. Sohaib Alam,
Zhihui Wang,
Stephen Jeffrey,
Bhuvanesh Sundar,
P. Aaron Lott,
Shon Grabbe,
Eleanor G. Rieffel,
Matthew J. Reagor,
Davide Venturelli
Abstract:
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 i…
▽ More
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.
△ Less
Submitted 2 May, 2024; v1 submitted 17 August, 2023;
originally announced August 2023.
-
Uplink MIMO Detection using Ising Machines: A Multi-Stage Ising Approach
Authors:
Abhishek Kumar Singh,
Ari Kapelyan,
Davide Venturelli,
Kyle Jamieson
Abstract:
Multiple-Input-Multiple-Output~(MIMO) signal detection is central to every state-of-the-art communication system, and enhancements in error performance and computation complexity of MIMO detection would significantly enhance data rate and latency experienced by the users. Theoretically, the optimal MIMO detector is the maximum-likelihood (ML) MIMO detector; however, due to its extremely high compl…
▽ More
Multiple-Input-Multiple-Output~(MIMO) signal detection is central to every state-of-the-art communication system, and enhancements in error performance and computation complexity of MIMO detection would significantly enhance data rate and latency experienced by the users. Theoretically, the optimal MIMO detector is the maximum-likelihood (ML) MIMO detector; however, due to its extremely high complexity, it is not feasible for large real-world communication systems. Over the past few years, algorithms based on physics-inspired Ising solvers, like Coherent Ising machines and Quantum Annealers, have shown significant performance improvements for the MIMO detection problem. However, the current state-of-the-art is limited to low-order modulations or systems with few users. In this paper, we propose an adaptive multi-stage Ising machine-based MIMO detector that extends the performance gains of physics-inspired computation to Large and Massive MIMO systems with a large number of users and very high modulation schemes~(up to 256-QAM). We enhance our previously proposed delta Ising formulation and develop a heuristic that adaptively optimizes the performance and complexity of our proposed method. We perform extensive micro-benchmarking to optimize several free parameters of the system and evaluate our methods' BER and spectral efficiency for Large and Massive MIMO systems (up to 32 users and 256 QAM modulation).
△ Less
Submitted 25 April, 2023;
originally announced April 2023.
-
A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms
Authors:
Robin Brown,
David E. Bernal Neira,
Davide Venturelli,
Marco Pavone
Abstract:
Recent years have seen significant advances in quantum/quantum-inspired technologies capable of approximately searching for the ground state of Ising spin Hamiltonians. The promise of leveraging such technologies to accelerate the solution of difficult optimization problems has spurred an increased interest in exploring methods to integrate Ising problems as part of their solution process, with ex…
▽ More
Recent years have seen significant advances in quantum/quantum-inspired technologies capable of approximately searching for the ground state of Ising spin Hamiltonians. The promise of leveraging such technologies to accelerate the solution of difficult optimization problems has spurred an increased interest in exploring methods to integrate Ising problems as part of their solution process, with existing approaches ranging from direct transcription to hybrid quantum-classical approaches rooted in existing optimization algorithms. While it is widely acknowledged that quantum computers should augment classical computers, rather than replace them entirely, comparatively little attention has been directed toward deriving analytical characterizations of their interactions. In this paper, we present a formal analysis of hybrid algorithms in the context of solving mixed-binary quadratic programs (MBQP) via Ising solvers. By leveraging an existing completely positive reformulation of MBQPs, as well as a new strong-duality result, we show the exactness of the dual problem over the cone of copositive matrices, thus allowing the resulting reformulation to inherit the straightforward analysis of convex optimization. We propose to solve this reformulation with a hybrid quantum-classical cutting-plane algorithm. Using existing complexity results for convex cutting-plane algorithms, we deduce that the classical portion of this hybrid framework is guaranteed to be polynomial time. This suggests that when applied to NP-hard problems, the complexity of the solution is shifted onto the subroutine handled by the Ising solver.
△ Less
Submitted 22 January, 2024; v1 submitted 27 July, 2022;
originally announced July 2022.
-
A Finite-Range Search Formulation of Maximum Likelihood MIMO Detection for Coherent Ising Machines
Authors:
Abhishek Kumar Singh,
Davide Venturelli,
Kyle Jamieson
Abstract:
The last couple of years have seen an emergence of physics-inspired computing for maximum likelihood MIMO detection. These methods involve transforming the MIMO detection problem into an Ising minimization problem, which can then be solved on an Ising Machine. Recent works have shown promising projections for MIMO wireless detection using Quantum Annealing optimizers and Coherent Ising Machines. W…
▽ More
The last couple of years have seen an emergence of physics-inspired computing for maximum likelihood MIMO detection. These methods involve transforming the MIMO detection problem into an Ising minimization problem, which can then be solved on an Ising Machine. Recent works have shown promising projections for MIMO wireless detection using Quantum Annealing optimizers and Coherent Ising Machines. While these methods perform very well for BPSK and 4-QAM, they struggle to provide good BER for 16-QAM and higher modulations. In this paper, we explore an enhanced CIM model, and propose a novel Ising formulation, which together are shown to be the first Ising solver that provides significant gains in the BER performance of large and massive MIMO systems, like $16\times16$ and $16\times32$, and sustain its performance gain even at 256-QAM modulation. We further perform a spectral efficiency analysis and show that, for a $16\times16$ MIMO with Adaptive Modulation and Coding, our method can provide substantial throughput gains over MMSE, achieving $2\times$ throughput for SNR $\leq25$ dB, and up to $1.5\times$ throughput for SNR $\geq 30$ dB.
△ Less
Submitted 10 May, 2022;
originally announced May 2022.
-
Ising Machines' Dynamics and Regularization for Near-Optimal Large and Massive MIMO Detection
Authors:
Abhishek Kumar Singh,
Kyle Jamieson,
Davide Venturelli,
Peter McMahon
Abstract:
Optimal MIMO detection has been one of the most challenging and computationally inefficient tasks in wireless systems. We show that the new analog computing techniques like Coherent Ising Machines (CIM) are promising candidates for performing near-optimal MIMO detection. We propose a novel regularized Ising formulation for MIMO detection that mitigates a common error floor problem and further evol…
▽ More
Optimal MIMO detection has been one of the most challenging and computationally inefficient tasks in wireless systems. We show that the new analog computing techniques like Coherent Ising Machines (CIM) are promising candidates for performing near-optimal MIMO detection. We propose a novel regularized Ising formulation for MIMO detection that mitigates a common error floor problem and further evolves it into an algorithm that achieves near-optimal MIMO detection. Massive MIMO systems, that have a large number of antennas at the Access point (AP), allow linear detectors to be near-optimal. However, the simplified detection in these systems comes at the cost of overall throughput, which could be improved by supporting more users. By means of numerical simulations, we show that in principle a MIMO detector based on a hybrid use of a CIM would allow us to add more transmitter antennas/users and increase the overall throughput of the cell by a significant factor. This would open up the opportunity to operate using more aggressive modulation and coding schemes and hence achieve high throughput: for a $16\times16$ large MIMO system, we estimate around 2.5$\times$ more throughput in mid-SNR regime ($\approx 12 dB$) and 2$\times$ more throughput in high-SNR regime( $>$ 20dB) than the industry standard, Minimum-Mean Square Error decoding (MMSE).
△ Less
Submitted 18 November, 2021; v1 submitted 21 May, 2021;
originally announced May 2021.
-
Physics-Inspired Heuristics for Soft MIMO Detection in 5G New Radio and Beyond
Authors:
Minsung Kim,
Salvatore Mandrà,
Davide Venturelli,
Kyle Jamieson
Abstract:
Overcoming the conventional trade-off between throughput and bit error rate (BER) performance, versus computational complexity is a long-term challenge for uplink Multiple-Input Multiple-Output (MIMO) detection in base station design for the cellular 5G New Radio roadmap, as well as in next generation wireless local area networks. In this work, we present ParaMax, a MIMO detector architecture that…
▽ More
Overcoming the conventional trade-off between throughput and bit error rate (BER) performance, versus computational complexity is a long-term challenge for uplink Multiple-Input Multiple-Output (MIMO) detection in base station design for the cellular 5G New Radio roadmap, as well as in next generation wireless local area networks. In this work, we present ParaMax, a MIMO detector architecture that for the first time brings to bear physics-inspired parallel tempering algorithmic techniques [28, 50, 67] on this class of problems. ParaMax can achieve near optimal maximum-likelihood (ML) throughput performance in the Large MIMO regime, Massive MIMO systems where the base station has additional RF chains, to approach the number of base station antennas, in order to support even more parallel spatial streams. ParaMax is able to achieve a near ML-BER performance up to 160x160 and 80x80 Large MIMO for low-order modulations such as BPSK and QPSK, respectively, only requiring less than tens of processing elements. With respect to Massive MIMO systems, in 12x24 MIMO with 16-QAM at SNR 16 dB, ParaMax achieves 330 Mbits/s near-optimal system throughput with 4--8 processing elements per subcarrier, which is approximately 1.4x throughput than linear detector-based Massive MIMO systems.
△ Less
Submitted 18 March, 2021;
originally announced March 2021.
-
Quantum Annealing for Large MIMO Downlink Vector Perturbation Precoding
Authors:
Srikar Kasi,
Abhishek Kumar Singh,
Davide Venturelli,
Kyle Jamieson
Abstract:
In a multi-user system with multiple antennas at the base station, precoding techniques in the downlink broadcast channel allow users to detect their respective data in a non-cooperative manner. Vector Perturbation Precoding (VPP) is a non-linear variant of transmit-side channel inversion that perturbs user data to achieve full diversity order. While promising, finding an optimal perturbation in V…
▽ More
In a multi-user system with multiple antennas at the base station, precoding techniques in the downlink broadcast channel allow users to detect their respective data in a non-cooperative manner. Vector Perturbation Precoding (VPP) is a non-linear variant of transmit-side channel inversion that perturbs user data to achieve full diversity order. While promising, finding an optimal perturbation in VPP is known to be an NP-hard problem, demanding heavy computational support at the base station and limiting the feasibility of the approach to small MIMO systems. This work proposes a radically different processing architecture for the downlink VPP problem, one based on Quantum Annealing (QA), to enable the applicability of VPP to large MIMO systems. Our design reduces VPP to a quadratic polynomial form amenable to QA, then refines the problem coefficients to mitigate the adverse effects of QA hardware noise. We evaluate our proposed QA based VPP (QAVP) technique on a real Quantum Annealing device over a variety of design and machine parameter settings. With existing hardware, QAVP can achieve a BER of $10^{-4}$ with 100$μ$s compute time, for a 6$\times$6 MIMO system using 64 QAM modulation at 32 dB SNR.
△ Less
Submitted 24 February, 2021;
originally announced February 2021.
-
Towards Hybrid Classical-Quantum Computation Structures in Wirelessly-Networked Systems
Authors:
Minsung Kim,
Davide Venturelli,
Kyle Jamieson
Abstract:
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 exis…
▽ More
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.
△ Less
Submitted 1 October, 2020;
originally announced October 2020.
-
Planning for Compilation of a Quantum Algorithm for Graph Coloring
Authors:
Minh Do,
Zhihui Wang,
Bryan O'Gorman,
Davide Venturelli,
Eleanor Rieffel,
Jeremy Frank
Abstract:
The problem of compiling general quantum algorithms for implementation on near-term quantum processors has been introduced to the AI community. Previous work demonstrated that temporal planning is an attractive approach for part of this compilationtask, specifically, the routing of circuits that implement the Quantum Alternating Operator Ansatz (QAOA) applied to the MaxCut problem on a quantum pro…
▽ More
The problem of compiling general quantum algorithms for implementation on near-term quantum processors has been introduced to the AI community. Previous work demonstrated that temporal planning is an attractive approach for part of this compilationtask, specifically, the routing of circuits that implement the Quantum Alternating Operator Ansatz (QAOA) applied to the MaxCut problem on a quantum processor architecture. In this paper, we extend the earlier work to route circuits that implement QAOA for Graph Coloring problems. QAOA for coloring requires execution of more, and more complex, operations on the chip, which makes routing a more challenging problem. We evaluate the approach on state-of-the-art hardware architectures from leading quantum computing companies. Additionally, we apply a planning approach to qubit initialization. Our empirical evaluation shows that temporal planning compares well to reasonable analytic upper bounds, and that solving qubit initialization with a classical planner generally helps temporal planners in finding shorter-makespan compilations for QAOA for Graph Coloring. These advances suggest that temporal planning can be an effective approach for more complex quantum computing algorithms and architectures.
△ Less
Submitted 22 February, 2020;
originally announced February 2020.
-
Leveraging Quantum Annealing for Large MIMO Processing in Centralized Radio Access Networks
Authors:
Minsung Kim,
Davide Venturelli,
Kyle Jamieson
Abstract:
User demand for increasing amounts of wireless capacity continues to outpace supply, and so to meet this demand, significant progress has been made in new MIMO wireless physical layer techniques. Higher-performance systems now remain impractical largely only because their algorithms are extremely computationally demanding. For optimal performance, an amount of computation that increases at an expo…
▽ More
User demand for increasing amounts of wireless capacity continues to outpace supply, and so to meet this demand, significant progress has been made in new MIMO wireless physical layer techniques. Higher-performance systems now remain impractical largely only because their algorithms are extremely computationally demanding. For optimal performance, an amount of computation that increases at an exponential rate both with the number of users and with the data rate of each user is often required. The base station's computational capacity is thus becoming one of the key limiting factors on wireless capacity. QuAMax is the first large MIMO centralized radio access network design to address this issue by leveraging quantum annealing on the problem. We have implemented QuAMax on the 2,031 qubit D-Wave 2000Q quantum annealer, the state-of-the-art in the field. Our experimental results evaluate that implementation on real and synthetic MIMO channel traces, showing that 10~$μ$s of compute time on the 2000Q can enable 48 user, 48 AP antenna BPSK communication at 20 dB SNR with a bit error rate of $10^{-6}$ and a 1,500 byte frame error rate of $10^{-4}$.
△ Less
Submitted 12 January, 2020;
originally announced January 2020.
-
Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
Authors:
Ryan Hamerly,
Takahiro Inagaki,
Peter L. McMahon,
Davide Venturelli,
Alireza Marandi,
Tatsuhiro Onodera,
Edwin Ng,
Carsten Langrock,
Kensuke Inaba,
Toshimori Honjo,
Koji Enbutsu,
Takeshi Umeki,
Ryoichi Kasahara,
Shoko Utsunomiya,
Satoshi Kako,
Ken-ichi Kawarabayashi,
Robert L. Byer,
Martin M. Fejer,
Hideo Mabuchi,
Dirk Englund,
Eleanor Rieffel,
Hiroki Takesue,
Yoshihisa Yamamoto
Abstract:
Physical annealing systems provide heuristic approaches to solving NP-hard Ising optimization problems. Here, we study the performance of two types of annealing machines--a commercially available quantum annealer built by D-Wave Systems, and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillator networks--on two classes of problems, the Sherrington-Kirkpatrick (…
▽ More
Physical annealing systems provide heuristic approaches to solving NP-hard Ising optimization problems. Here, we study the performance of two types of annealing machines--a commercially available quantum annealer built by D-Wave Systems, and measurement-feedback coherent Ising machines (CIMs) based on optical parametric oscillator networks--on two classes of problems, the Sherrington-Kirkpatrick (SK) model and MAX-CUT. The D-Wave quantum annealer outperforms the CIMs on MAX-CUT on regular graphs of degree 3. On denser problems, however, we observe an exponential penalty for the quantum annealer ($\exp(-α_\textrm{DW} N^2)$) relative to CIMs ($\exp(-α_\textrm{CIM} N)$) for fixed anneal times, on both the SK model and on 50%-edge-density MAX-CUT, where the coefficients $α_\textrm{CIM}$ and $α_\textrm{DW}$ are problem-class-dependent. On instances with over $50$ vertices, a several-orders-of-magnitude time-to-solution difference exists between CIMs and the D-Wave annealer. An optimal-annealing-time analysis is also consistent with a significant projected performance difference. The difference in performance between the sparsely connected D-Wave machine and the measurement-feedback facilitated all-to-all connectivity of the CIMs provides strong experimental support for efforts to increase the connectivity of quantum annealers.
△ Less
Submitted 24 May, 2019; v1 submitted 14 May, 2018;
originally announced May 2018.
-
Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation
Authors:
Kyle E. C. Booth,
Minh Do,
J. Christopher Beck,
Eleanor Rieffel,
Davide Venturelli,
Jeremy Frank
Abstract:
Recently, the makespan-minimization problem of compiling a general class of quantum algorithms into near-term quantum processors has been introduced to the AI community. The research demonstrated that temporal planning is a strong approach for a class of quantum circuit compilation (QCC) problems. In this paper, we explore the use of constraint programming (CP) as an alternative and complementary…
▽ More
Recently, the makespan-minimization problem of compiling a general class of quantum algorithms into near-term quantum processors has been introduced to the AI community. The research demonstrated that temporal planning is a strong approach for a class of quantum circuit compilation (QCC) problems. In this paper, we explore the use of constraint programming (CP) as an alternative and complementary approach to temporal planning. We extend previous work by introducing two new problem variations that incorporate important characteristics identified by the quantum computing community. We apply temporal planning and CP to the baseline and extended QCC problems as both stand-alone and hybrid approaches. Our hybrid methods use solutions found by temporal planning to warm start CP, leveraging the ability of the former to find satisficing solutions to problems with a high degree of task optionality, an area that CP typically struggles with. The CP model, benefiting from inferred bounds on planning horizon length and task counts provided by the warm start, is then used to find higher quality solutions. Our empirical evaluation indicates that while stand-alone CP is only competitive for the smallest problems, CP in our hybridization with temporal planning out-performs stand-alone temporal planning in the majority of problem classes.
△ Less
Submitted 18 March, 2018;
originally announced March 2018.
-
Quantum Annealing Applied to De-Conflicting Optimal Trajectories for Air Traffic Management
Authors:
Tobias Stollenwerk,
Bryan O'Gorman,
Davide Venturelli,
Salvatore Mandrà,
Olga Rodionova,
Hok K. Ng,
Banavar Sridhar,
Eleanor G. Rieffel,
Rupak Biswas
Abstract:
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…
▽ More
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.
△ Less
Submitted 20 February, 2019; v1 submitted 13 November, 2017;
originally announced November 2017.
-
Compiling quantum circuits to realistic hardware architectures using temporal planners
Authors:
Davide Venturelli,
Minh Do,
Eleanor Rieffel,
Jeremy Frank
Abstract:
To run quantum algorithms on emerging gate-model quantum hardware, quantum circuits must be compiled to take into account constraints on the hardware. For near-term hardware, with only limited means to mitigate decoherence, it is critical to minimize the duration of the circuit. We investigate the application of temporal planners to the problem of compiling quantum circuits to newly emerging quant…
▽ More
To run quantum algorithms on emerging gate-model quantum hardware, quantum circuits must be compiled to take into account constraints on the hardware. For near-term hardware, with only limited means to mitigate decoherence, it is critical to minimize the duration of the circuit. We investigate the application of temporal planners to the problem of compiling quantum circuits to newly emerging quantum hardware. While our approach is general, we focus on compiling to superconducting hardware architectures with nearest neighbor constraints. Our initial experiments focus on compiling Quantum Alternating Operator Ansatz (QAOA) circuits whose high number of commuting gates allow great flexibility in the order in which the gates can be applied. That freedom makes it more challenging to find optimal compilations but also means there is a greater potential win from more optimized compilation than for less flexible circuits. We map this quantum circuit compilation problem to a temporal planning problem, and generated a test suite of compilation problems for QAOA circuits of various sizes to a realistic hardware architecture. We report compilation results from several state-of-the-art temporal planners on this test set. This early empirical evaluation demonstrates that temporal planning is a viable approach to quantum circuit compilation.
△ Less
Submitted 21 December, 2017; v1 submitted 24 May, 2017;
originally announced May 2017.
