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:2208.05181 · IEEE Transactions on Quantum Engineering

Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem

Yuki Sano, Masaya Norimoto, Naoki Ishikawa

Published Jan 1, 2023• 19 citations
arXivHTMLPDF

Abstract

In this paper, we propose a novel method of formulating an NP-hard wireless channel assignment problem as a higher-order unconstrained binary optimization (HUBO), where the Grover adaptive search (GAS) is used to provide a quadratic speedup for solving the problem. The conventional method relies on a one-hot encoding of the channel indices, resulting in a quadratic formulation. By contrast, we conceive ascending and descending binary encodings of the channel indices, construct a specific quantum circuit, and derive the exact numbers of qubits and gates required by GAS. Our analysis clarifies that the proposed HUBO formulation significantly reduces the number of qubits and the query complexity compared with the conventional quadratic formulation. This advantage is achieved at the cost of an increased number of quantum gates, which we demonstrate can be reduced by our proposed descending binary encoding.

DOI
10.1109/tqe.2023.3293452

Related papers

Grover Adaptive Search for the Higher-Order Formulation of Quadratic Assignment Problems

Taku Mikuriya, Shintaro Fujiwara, Kein Yukiyoshi +2 more

We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective.

arXiv:2410.12181•Oct 16, 2024•0 citations

Resource-Efficient Quantum Optimization via Higher-Order Encoding

Frederik Koch, Shahram Panahiyan, Rick Mukherjee +2 more

Quantum approaches to combinatorial optimization problems (COPs) are often limited by the resource demands of Quadratic Unconstrained Binary Optimization (QUBO) encodings, which enlarge circuits through penalty terms and increase qubit and gate counts. We show that Higher-Order Unconstrained Binary Optimization (HUBO) enables a more resource-efficient formulation. Our method systematically constructs HUBO Hamiltonians and, compared to a QUBO formulation in benchmarks on Gate Assignment (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP) problems, significantly reduces qubit requirements and decreases total CNOT gate counts by at least 89.6% for all tested instances. These results highlight HUBO as a practical alternative for quantum optimization on near-term devices. To promote adoption, we release an open-source Python library that automates HUBO model construction, extends beyond the examples presented in this work, and broadens access to resource-efficient quantum optimization.

quant-pharXiv:2511.17545•EPJ Quantum Technology•Nov 11, 2025•0 citations

Quantum Algorithm for Higher-Order Unconstrained Binary Optimization and MIMO Maximum Likelihood Detection

Masaya Norimoto, Ryuhei Mori, Naoki Ishikawa

In this paper, we propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization (HUBO) problem. This algorithm is based on the Grover adaptive search that originally supported HUBO with integer coefficients. Next, as an application example, we formulate multiple-input multiple-output maximum likelihood detection as a HUBO problem with real-valued coefficients, where we use the Gray-coded bit-to-symbol mapping specified in the 5G standard. The proposed approach allows us to construct an efficient quantum circuit for the detection problem and to analyze specific numbers of required qubits and quantum gates, whereas other conventional studies have assumed that such a circuit is feasible as a quantum oracle. To further accelerate the quantum algorithm, we also derive a probability distribution of the objective function value and determine a unique threshold to sample better states. Assuming a future fault-tolerant quantum computing, our proposed algorithm has the potential for significantly reducing query complexity in the classical domain and providing a quadratic speedup in the quantum domain.

arXiv:2205.15478•IEEE Transactions on Communications•Feb 14, 2023•33 citations

Quantum Speedup of the Dispersion and Codebook Design Problems

Kein Yukiyoshi, Taku Mikuriya, Hyeon Seok Rou +2 more

In this article, we propose new formulations of max-sum and max-min dispersion problems that enable solutions via the Grover adaptive search (GAS) quantum algorithm, offering quadratic speedup. Dispersion problems are combinatorial optimization problems classified as NP-hard, which appear often in coding theory and wireless communications applications involving optimal codebook design. In turn, GAS is a quantum exhaustive search algorithm that can be used to implement full-fledged maximum-likelihood optimal solutions. In conventional naive formulations, however, it is typical to rely on a binary vector spaces, resulting in search space sizes prohibitive even for GAS. To circumvent this challenge, we instead formulate the search of optimal dispersion problem over Dicke states, an equal superposition of binary vectors with equal Hamming weights, which significantly reduces the search space leading to a simplification of the quantum circuit via the elimination of penalty terms. In addition, we propose a method to replace distance coefficients with their ranks, contributing to the reduction of the number of qubits. Our analysis demonstrates that as a result of the proposed techniques, a reduction in query complexity compared to the conventional GAS using the Hadamard transform is achieved, enhancing the feasibility of the quantum-based solution of the dispersion problem.

arXiv:2406.07187•IEEE Transactions on Quantum Engineering•Jan 1, 2024•12 citations

Accelerating Grover Adaptive Search: Qubit and Gate Count Reduction Strategies With Higher Order Formulations

Yuki Sano, Kosuke Mitarai, Naoki Yamamoto +1 more

Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. In this article, we propose higher order binary formulations that can simultaneously reduce the numbers of qubits and gates required for GAS. Specifically, we consider two novel strategies: one that reduces the number of gates through polynomial factorization, and the other that halves the order of the objective function, subsequently decreasing circuit runtime and implementation cost. Our analysis demonstrates that the proposed higher order formulations improve the convergence performance of GAS by reducing both the search space size and the number of quantum gates. Our strategies are also beneficial for general combinatorial optimization problems using one-hot encoding.

arXiv:2308.01572•IEEE Transactions on Quantum Engineering•Jan 1, 2024•17 citations

The Grover Adaptive Search Algorithm as a Solver: High-Order Unconstrained Binary Optimization Problems

Le Manh Quan Tran

High-order binary optimization (HUBO) formulation can represent many real world problems. This mathematical approach is particularly relevant within the quantum computation domain because quantum hardware allows to directly map and solve these problems. The thesis explores the implementation of Grover Adaptive Search (GAS) by varying the different free parameters to evaluate the quality of the solution and the success rate of the algorithm, along with a possible optimization procedure. In particular, GAS is an algorithm that is compliant with HUBO and theoretically offer a quadratic speed up over classical computation. This thesis implements a quantum circuit for GAS algorithm to solve a 4-city traveling salesman problem along with two strategies to reduce the gate counts. The results include the output quality of the value of the objective function and the success rate of reaching the true minimum of 7, where the optimal configuration achieves an average value of 9.4 and a success rate of 36%. This configuration also maintains a 7% lower average value and a 10% higher success rate compared to randomly generated parameters.

•Apr 24, 2026•0 citations
In this paper, we propose a novel method of formulating an NP-hard wireless channel assignment problem as a higher-order unconstrained binary optimization (HUBO), where the Grover adaptive search (GAS) is used to provide a quadratic speedup for solving the problem. The conventional method relies on a one-hot encoding of the channel indices, resulting in a quadratic formulation. By contrast, we conceive ascending and descending binary encodings of the channel indices, construct a specific quantum circuit, and derive the exact numbers of qubits and gates required by GAS. Our analysis clarifies that the proposed HUBO formulation significantly reduces the number of qubits and the query complexity compared with the conventional quadratic formulation. This advantage is achieved at the cost of an increased number of quantum gates, which we demonstrate can be reduced by our proposed descending binary encoding.
We demonstrate that the search space of the quadratic assignment problem (QAP), known as an NP-hard combinatorial optimization problem, can be reduced using Grover adaptive search (GAS) with permutation preparation operator (PPO). To that end, we first revise the traditional quadratic unconstrained binary optimization (QUBO) formulation of the QAP into a higher-order unconstrained binary optimization (HUBO) formulation, introducing a binary encoding method. Algebraic analyses in terms of the number of qubits, quantum gates, circuit depth, and query complexity are performed, which indicate that our proposed approach significantly reduces the search space size, improving convergence performance to the optimal solution compared to the conventional one. Furthermore, although the PPO for HUBO has a greater circuit depth than the PPO for QUBO, when the analysis is extended to the entire state preparation operator, both HUBO and QUBO exhibit comparable depths. Therefore, owing to its smaller number of variables, HUBO can be concluded to be more effective.
Quantum approaches to combinatorial optimization problems (COPs) are often limited by the resource demands of Quadratic Unconstrained Binary Optimization (QUBO) encodings, which enlarge circuits through penalty terms and increase qubit and gate counts. We show that Higher-Order Unconstrained Binary Optimization (HUBO) enables a more resource-efficient formulation. Our method systematically constructs HUBO Hamiltonians and, compared to a QUBO formulation in benchmarks on Gate Assignment (GAP), Maximum k-Colorable Subgraph (MkCS), and Integer Programming (IP) problems, significantly reduces qubit requirements and decreases total CNOT gate counts by at least 89.6% for all tested instances. These results highlight HUBO as a practical alternative for quantum optimization on near-term devices. To promote adoption, we release an open-source Python library that automates HUBO model construction, extends beyond the examples presented in this work, and broadens access to resource-efficient quantum optimization.
In this paper, we propose a quantum algorithm that supports a real-valued higher-order unconstrained binary optimization (HUBO) problem. This algorithm is based on the Grover adaptive search that originally supported HUBO with integer coefficients. Next, as an application example, we formulate multiple-input multiple-output maximum likelihood detection as a HUBO problem with real-valued coefficients, where we use the Gray-coded bit-to-symbol mapping specified in the 5G standard. The proposed approach allows us to construct an efficient quantum circuit for the detection problem and to analyze specific numbers of required qubits and quantum gates, whereas other conventional studies have assumed that such a circuit is feasible as a quantum oracle. To further accelerate the quantum algorithm, we also derive a probability distribution of the objective function value and determine a unique threshold to sample better states. Assuming a future fault-tolerant quantum computing, our proposed algorithm has the potential for significantly reducing query complexity in the classical domain and providing a quadratic speedup in the quantum domain.
In this article, we propose new formulations of max-sum and max-min dispersion problems that enable solutions via the Grover adaptive search (GAS) quantum algorithm, offering quadratic speedup. Dispersion problems are combinatorial optimization problems classified as NP-hard, which appear often in coding theory and wireless communications applications involving optimal codebook design. In turn, GAS is a quantum exhaustive search algorithm that can be used to implement full-fledged maximum-likelihood optimal solutions. In conventional naive formulations, however, it is typical to rely on a binary vector spaces, resulting in search space sizes prohibitive even for GAS. To circumvent this challenge, we instead formulate the search of optimal dispersion problem over Dicke states, an equal superposition of binary vectors with equal Hamming weights, which significantly reduces the search space leading to a simplification of the quantum circuit via the elimination of penalty terms. In addition, we propose a method to replace distance coefficients with their ranks, contributing to the reduction of the number of qubits. Our analysis demonstrates that as a result of the proposed techniques, a reduction in query complexity compared to the conventional GAS using the Hadamard transform is achieved, enhancing the feasibility of the quantum-based solution of the dispersion problem.
Grover adaptive search (GAS) is a quantum exhaustive search algorithm designed to solve binary optimization problems. In this article, we propose higher order binary formulations that can simultaneously reduce the numbers of qubits and gates required for GAS. Specifically, we consider two novel strategies: one that reduces the number of gates through polynomial factorization, and the other that halves the order of the objective function, subsequently decreasing circuit runtime and implementation cost. Our analysis demonstrates that the proposed higher order formulations improve the convergence performance of GAS by reducing both the search space size and the number of quantum gates. Our strategies are also beneficial for general combinatorial optimization problems using one-hot encoding.
High-order binary optimization (HUBO) formulation can represent many real world problems. This mathematical approach is particularly relevant within the quantum computation domain because quantum hardware allows to directly map and solve these problems. The thesis explores the implementation of Grover Adaptive Search (GAS) by varying the different free parameters to evaluate the quality of the solution and the success rate of the algorithm, along with a possible optimization procedure. In particular, GAS is an algorithm that is compliant with HUBO and theoretically offer a quadratic speed up over classical computation. This thesis implements a quantum circuit for GAS algorithm to solve a 4-city traveling salesman problem along with two strategies to reduce the gate counts. The results include the output quality of the value of the objective function and the success rate of reaching the true minimum of 7, where the optimal configuration achieves an average value of 9.4 and a success rate of 36%. This configuration also maintains a 7% lower average value and a 10% higher success rate compared to randomly generated parameters.