Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2305.17953 · IET Radar Sonar & Navigation

Phase‐coded radar waveform design with quantum annealing

Timothé Presles, Cyrille Enderli, Gilles Burel, El Houssaïn Baghious

Published Oct 18, 2023• 0 citations
arXivHTMLPDF

Abstract

Abstract The Integrated Side Lobe Ratio (ISLR) problem the authors consider here consists in finding optimal sequences of phase shifts in order to minimise the mean squared cross‐correlation side lobes of a transmitted radar signal and a mismatched replica. Currently, ISLR does not seem to be easier than the general polynomial unconstrained binary problem, which is NP‐hard. In their work, the authors aim to take advantage of the scalability of quantum computing to find new optima, by solving the ISLR problem on a quantum annealer. This quantum device is designed to solve quadratic optimisation problems with binary variables (QUBO). After proposing suitable formulation for different instances of the ISLR, the authors discuss the performances and the scalability of their approach on the D‐Wave quantum computer. More broadly, their work enlightens the limits and potential of the adiabatic quantum computation for the solving of large instances of combinatorial optimisation problems.

DOI
10.1049/rsn2.12490

Related papers

Phase-coded radar waveform AI-based augmented engineering and optimal design by Quantum Annealing

Timothé Presles, Cyrille Enderli, Rémi Bricout +2 more

The Integrated Side Lobe Ratio (ISLR) problem we consider here consists in finding optimal sequences of phase shifts in order to minimize the mean squared cross-correlation sidelobes of a transmitted radar signal and a mismatched replica. Given a finite set of quantized phase shifts, the exponentially increasing number of possible sequences leads to long-time processing and approximated results. Currently, ISLR does not seem to be easier than the general polynomial unconstrained binary problem, which is NP-hard. Our contribution is to implement this problem on a Quantum Annealer, a kind of Quantum Computer designed to solve quadratic optimization problems with binary variables. We cast the problem in a suitable formulation to be run on the available DWave quantum device and discuss the performances. Our work shows two limiting factors for scalability: A hardware related one and constraint implementation in the QUBO formulation. More broadly, this study enlightens the limits and the potential of Adiabatic Quantum Computation in terms of speedup and high-scaled resolution of a class of combinatory optimization problems.

•Aug 9, 2021•0 citations

Synthetic aperture radar image segmentation with quantum annealing

Timothé Presles, Cyrille Enderli, Gilles Burel +1 more

Abstract In image processing, image segmentation is the process of partitioning a digital image into multiple image segments. Among state‐of‐the‐art methods, Markov random fields can be used to model dependencies between pixels and achieve a segmentation by minimising an associated cost function. Currently, finding the optimal set of segments for a given image modelled as a Markov random fields appears to be NP‐hard. The authors aim to take advantage of the exponential scalability of quantum computing to speed up the segmentation of synthetic aperture radar images. For that purpose, the authors propose a hybrid quantum annealing classical optimisation expectation maximisation algorithm to obtain optimal sets of segments. After proposing suitable formulations, the authors discuss the performances and the scalability of authors’ approach on the D‐Wave quantum computer. The authors also propose a short study of optimal computation parameters to enlighten the limits and potential of the adiabatic quantum computation to solve large instances of combinatorial optimisation problems.

arXiv:2305.17954•IET Radar Sonar & Navigation•Jan 2, 2024•6 citations

Embedding Equality Constraints of Optimization Problems into a Quantum Annealer

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type ∑ x i = k for binary variables x i. Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k.

Algorithms•Apr 17, 2019•22 citations

Simple Constraint Embedding for Quantum Annealers

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as the D-Wave 2X computer are designed to natively solve Quadratic Unconstrained Binary Optimization (QUBO) problems to optimality or near optimality. Most NP-hard problems, which are hard for classical computers, can be naturally described as quadratic binary problems that contain a quadratic binary objective function and one or more constraints. Since a QUBO cannot have constraints, each such constraint has to be added to the objective function as a penalty, in order to solve on D-Wave. For a minimization problem, for instance, such penalty can be a quadratic term that gets a value zero, if the constraint is satisfied, and a large value, if it is not. In many cases, however, the penalty can significantly increase the number of quadratic terms in the resulting QUBO and make it too large to embed into the D-Wave hardware. In this paper, we develop an alternative method for formulating and embedding constraints of the type Σi=1sxi=1, which is much more scalable than the existing ones, and analyze the properties of the resulting embeddings.

IEEE International Conference on Rebooting Computing (ICRC)•Nov 1, 2018•9 citations

FPGA-Placement via Quantum Annealing

Thore Gerlach, Stefan Knipp, David Biesner +3 more

In this work we explore the use of quantum computers in solving the NP-hard placement problem of the Field-Programmable Gate Array (FPGA) implementation phase and introduce a novel approach suited for current quantum hardware sizes. Adiabatic quantum computing (AQC), with its capability to traverse expansive solution spaces, is a good fit for addressing this combinatorial problem with its exponentially large solution space. Instead of solving a single the whole problem at once, we re-formulate the placement problem as a series of so called quadratic unconstrained binary optimization (QUBO) problems which are subsequently solved via AQC. Our novel formulation facilitates a straight-forward integration of design constraints. Moreover, the size of the sub-problems can be conveniently adapted to the available hardware capabilities. Beside the sole proposal of a novel method, we ask whether contemporary quantum hardware is resilient enough to find placements for real-world-sized FPGAs. A numerical evaluation on a D-Wave Advantage 5.4 quantum annealer suggests that the answer is in the affirmative.

arXiv:2312.15467•ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA)•Apr 1, 2024•2 citations

A quantum annealing approach for boolean satisfiability problem

Juexiao Su, Tianheng Tu, Lei He

Quantum annealing device has shown a great potential in solving discrete problems that are theoretically and empirically hard. Boolean Satisfiability (SAT) problem, determining if there is an assignment of variables that satisfies a given Boolean function, is the first proven NP-complete problem widely used in various domains. Here, we present a novel mapping of the SAT problem to the quadratic unconstrained binary optimization problem (QUBO), and further develop a tool flow embedding the proposed QUBO to the architecture of the commercialized quantum computer D-Wave. By leveraging electronic design automation techniques including synthesis, placement and routing, this is not only the first work providing the detail flow that embeds the QUBO, but also a technique scalable for real world applications and some hard SAT problems with over 6000 variables in QUBO. Based on our results, we discuss the challenges in solving SAT using the current generation of annealing device, and explore the problem solving capability of future quantum annealing computers.

ACM/IEEE Design Automation Conference (DAC)•May 25, 2016•39 citations
Abstract The Integrated Side Lobe Ratio (ISLR) problem the authors consider here consists in finding optimal sequences of phase shifts in order to minimise the mean squared cross‐correlation side lobes of a transmitted radar signal and a mismatched replica. Currently, ISLR does not seem to be easier than the general polynomial unconstrained binary problem, which is NP‐hard. In their work, the authors aim to take advantage of the scalability of quantum computing to find new optima, by solving the ISLR problem on a quantum annealer. This quantum device is designed to solve quadratic optimisation problems with binary variables (QUBO). After proposing suitable formulation for different instances of the ISLR, the authors discuss the performances and the scalability of their approach on the D‐Wave quantum computer. More broadly, their work enlightens the limits and potential of the adiabatic quantum computation for the solving of large instances of combinatorial optimisation problems.
The Integrated Side Lobe Ratio (ISLR) problem we consider here consists in finding optimal sequences of phase shifts in order to minimize the mean squared cross-correlation sidelobes of a transmitted radar signal and a mismatched replica. Given a finite set of quantized phase shifts, the exponentially increasing number of possible sequences leads to long-time processing and approximated results. Currently, ISLR does not seem to be easier than the general polynomial unconstrained binary problem, which is NP-hard. Our contribution is to implement this problem on a Quantum Annealer, a kind of Quantum Computer designed to solve quadratic optimization problems with binary variables. We cast the problem in a suitable formulation to be run on the available DWave quantum device and discuss the performances. Our work shows two limiting factors for scalability: A hardware related one and constraint implementation in the QUBO formulation. More broadly, this study enlightens the limits and the potential of Adiabatic Quantum Computation in terms of speedup and high-scaled resolution of a class of combinatory optimization problems.
Abstract In image processing, image segmentation is the process of partitioning a digital image into multiple image segments. Among state‐of‐the‐art methods, Markov random fields can be used to model dependencies between pixels and achieve a segmentation by minimising an associated cost function. Currently, finding the optimal set of segments for a given image modelled as a Markov random fields appears to be NP‐hard. The authors aim to take advantage of the exponential scalability of quantum computing to speed up the segmentation of synthetic aperture radar images. For that purpose, the authors propose a hybrid quantum annealing classical optimisation expectation maximisation algorithm to obtain optimal sets of segments. After proposing suitable formulations, the authors discuss the performances and the scalability of authors’ approach on the D‐Wave quantum computer. The authors also propose a short study of optimal computation parameters to enlighten the limits and potential of the adiabatic quantum computation to solve large instances of combinatorial optimisation problems.
Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type ∑ x i = k for binary variables x i. Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k.
Quantum annealers such as the D-Wave 2X computer are designed to natively solve Quadratic Unconstrained Binary Optimization (QUBO) problems to optimality or near optimality. Most NP-hard problems, which are hard for classical computers, can be naturally described as quadratic binary problems that contain a quadratic binary objective function and one or more constraints. Since a QUBO cannot have constraints, each such constraint has to be added to the objective function as a penalty, in order to solve on D-Wave. For a minimization problem, for instance, such penalty can be a quadratic term that gets a value zero, if the constraint is satisfied, and a large value, if it is not. In many cases, however, the penalty can significantly increase the number of quadratic terms in the resulting QUBO and make it too large to embed into the D-Wave hardware. In this paper, we develop an alternative method for formulating and embedding constraints of the type Σi=1sxi=1, which is much more scalable than the existing ones, and analyze the properties of the resulting embeddings.
In this work we explore the use of quantum computers in solving the NP-hard placement problem of the Field-Programmable Gate Array (FPGA) implementation phase and introduce a novel approach suited for current quantum hardware sizes. Adiabatic quantum computing (AQC), with its capability to traverse expansive solution spaces, is a good fit for addressing this combinatorial problem with its exponentially large solution space. Instead of solving a single the whole problem at once, we re-formulate the placement problem as a series of so called quadratic unconstrained binary optimization (QUBO) problems which are subsequently solved via AQC. Our novel formulation facilitates a straight-forward integration of design constraints. Moreover, the size of the sub-problems can be conveniently adapted to the available hardware capabilities. Beside the sole proposal of a novel method, we ask whether contemporary quantum hardware is resilient enough to find placements for real-world-sized FPGAs. A numerical evaluation on a D-Wave Advantage 5.4 quantum annealer suggests that the answer is in the affirmative.
Quantum annealing device has shown a great potential in solving discrete problems that are theoretically and empirically hard. Boolean Satisfiability (SAT) problem, determining if there is an assignment of variables that satisfies a given Boolean function, is the first proven NP-complete problem widely used in various domains. Here, we present a novel mapping of the SAT problem to the quadratic unconstrained binary optimization problem (QUBO), and further develop a tool flow embedding the proposed QUBO to the architecture of the commercialized quantum computer D-Wave. By leveraging electronic design automation techniques including synthesis, placement and routing, this is not only the first work providing the detail flow that embeds the QUBO, but also a technique scalable for real world applications and some hard SAT problems with over 6000 variables in QUBO. Based on our results, we discuss the challenges in solving SAT using the current generation of annealing device, and explore the problem solving capability of future quantum annealing computers.