It's Quick to be Square: Fast Quadratisation for Quantum Toolchains

• URL: http://arxiv.org/abs/2411.19934v2
• Date: Fri, 06 Dec 2024 17:56:33 GMT
• Title: It's Quick to be Square: Fast Quadratisation for Quantum Toolchains
• Authors: Lukas Schmidbauer, Elisabeth Lobe, Ina Schaefer, Wolfgang Mauerer,
• Abstract summary: We consider a specific class of higher-level representations, i.e. unconstrained binary problems. We devise novel automatic transformation mechanisms into widely used unconstrained binary optimisation problems. We also identify what influence factors of lower-level details can be abstracted away in the transformation process.
• Score: 5.023742533119026
• License:
• Abstract: Many of the envisioned use-cases for quantum computers involve optimisation processes. While there are many algorithmic primitives to perform the required calculations, all eventually lead to quantum gates operating on quantum bits, with an order as determined by the structure of the objective function and the properties of target hardware. When the structure of the problem representation is not aligned with structure and boundary conditions of the executing hardware, various overheads degrading the computation may arise, possibly negating any possible quantum advantage. Therefore, automatic transformations of problem representations play an important role in quantum computing when descriptions (semi-)targeted at humans must be cast into forms that can be executed on quantum computers. Mathematically equivalent formulations are known to result in substantially different non-functional properties depending on hardware, algorithm and detail properties of the problem. Given the current state of noisy intermediate-scale quantum (NISQ) hardware, these effects are considerably more pronounced than in classical computing. Likewise, efficiency of the transformation itself is relevant because possible quantum advantage may easily be eradicated by the overhead of transforming between representations. In this paper, we consider a specific class of higher-level representations, i.e. polynomial unconstrained binary optimisation problems, and devise novel automatic transformation mechanisms into widely used quadratic unconstrained binary optimisation problems that substantially improve efficiency and versatility over the state of the art. We also identify what influence factors of lower-level details can be abstracted away in the transformation process, and which details must be made available to higher-level abstractions.

Related papers

• Combinatorial Optimization with Quantum Computers [1.199955563466263]
  Quantum computers do computation with a potential advantage over classical computers. A quantum computer can apply the operator to a superposition of binary strings to provide a superposition of binary outputs. A family of quantum machines called quantum annealers are specially designed to solve optimization problems.
  arXiv  Detail & Related papers  (2024-12-20T10:46:18Z)
• Codesigned counterdiabatic quantum optimization on a photonic quantum processor [6.079051215256144]
  We focus on the counterdiabatic protocol with a codesigned approach to implement this algorithm on a photonic quantum processor. We develop and implement an optimized counterdiabatic method by tackling the higher-order many-body interaction terms. We experimentally demonstrate the advantages of a codesigned mapping of counterdiabatic quantum dynamics for quantum computing on photonic platforms.
  arXiv  Detail & Related papers  (2024-09-26T15:08:19Z)
• Polynomial Reduction Methods and their Impact on QAOA Circuits [2.4588375162098877]
  We show how higher-order problem formulations can be used to leverage different desired non-functional properties for quantum optimisation. Our study shows that the approach allows us to satisfy different trade-offs, and suggests various possibilities for the future construction of general-purpose abstractions.
  arXiv  Detail & Related papers  (2024-06-13T07:43:18Z)
• Computable and noncomputable in the quantum domain: statements and conjectures [0.70224924046445]
  We consider an approach to the question of describing a class of problems whose solution can be accelerated by a quantum computer. The unitary operation that transforms the initial quantum state into the desired one must be decomposable into a sequence of one- and two-qubit gates.
  arXiv  Detail & Related papers  (2024-03-25T15:47:35Z)
• Towards Quantum Computational Mechanics [1.530480694206666]
  We show how quantum computing can be used to solve representative element volume (RVE) problems in computational homogenisation. Our quantum RVE solver attains exponential acceleration with respect to classical solvers.
  arXiv  Detail & Related papers  (2023-12-06T12:53:02Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  The anticipated applications of quantum computers span across science and industry. We present a survey of several potential application areas of quantum algorithms. We outline the challenges and opportunities in each area in an "end-to-end" fashion.
  arXiv  Detail & Related papers  (2023-10-04T17:53:55Z)
• Optimizing quantum gates towards the scale of logical qubits [78.55133994211627]
  A foundational assumption of quantum gates theory is that quantum gates can be scaled to large processors without exceeding the error-threshold for fault tolerance. Here we report on a strategy that can overcome such problems. We demonstrate it by choreographing the frequency trajectories of 68 frequency-tunablebits to execute single qubit while superconducting errors.
  arXiv  Detail & Related papers  (2023-08-04T13:39:46Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.