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:2205.15478 · IEEE Transactions on Communications

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

Masaya Norimoto, Ryuhei Mori, Naoki Ishikawa

Published Feb 14, 2023• 33 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tcomm.2023.3244924

Related papers

Qubit Reduction and Quantum Speedup for Wireless Channel Assignment Problem

Yuki Sano, Masaya Norimoto, Naoki Ishikawa

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.

arXiv:2208.05181•IEEE Transactions on Quantum Engineering•Jan 1, 2023•19 citations

Grover Adaptive Search for Joint Maximum-Likelihood Detection of Power-Domain Non-Orthogonal Multiple Access

Masaya Norimoto, Naoki Ishikawa

In this paper, we address the joint maximum-likelihood detection of power-domain non-orthogonal multiple access and transform the detection problem into a binary optimization problem. Then, we solve it by a quantum algorithm, Grover adaptive search (GAS), and further accelerate the algorithm. Assuming fault-tolerant quantum computing, GAS provides a quadratic speedup for binary optimization problems in terms of query complexity. The proposed method designs the number of Grover operators using a time-invariant distribution of the number of solutions, which can be obtained in advance. Simulation results demonstrate that the proposed method is capable of reducing the query complexity in the classical domain while achieving the optimal performance.

IEEE Vehicular Technology Conference•Jun 1, 2023•2 citations

Quantum-Native Maximum Likelihood Detection in Random Access Channel with Overloaded MIMO

Hyoga Iizumi, Naoki Ishikawa, Shunsuke Uehashi +3 more

In this paper, we propose a quantum-native formulation of maximum likelihood detection (MLD) for overloaded multiple-input multiple-output (MIMO) systems in a random access channel, where numerous user terminals share the same channel resource and asynchronously transmit signals. Classical linear detectors suffer from significant performance degradation in this scenario, whereas the exhaustive-search MLD achieves the optimal performance but incurs an exponential computational complexity. To overcome this trade-off, we formulate the MLD as a binary optimization problem and solve it via Grover adaptive search (GAS) -- a quantum exhaustive search algorithm offering quadratic speedup in fault-tolerant quantum computing. We then introduce a search space reduction technique to substantially decrease the required computational resources. In addition, we investigate efficient parameter settings for GAS through probability analysis to improve convergence performance. We demonstrate that the proposed detector achieves the optimal detection performance while reducing the required Grover rotation count to reach the solution by up to approximately 65% compared with the conventional GAS, showing its potential as a viable solution for future quantum-accelerated wireless systems.

eess.SPCross-listedarXiv:2605.19389•May 20, 2026•0 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

Quantum-Native Formulation of Maximum Likelihood Detection in Random Access Channel with Overloaded MIMO

Hyoga Iizumi, Naoki Ishikawa, Shunsuke Uehashi +3 more

In this paper, we propose a quantum-native formulation of maximum likelihood detection in random access channel with overloaded multiple-input multiple-output (MIMO), where a number of user terminals share the same channel resource and asynchronously transmit signals. Classical low-complexity linear detectors suffer from significant performance degradation in this scenario, while the exhaustive-search-based maximum likelihood detection achieves the optimal performance but induces an exponential increase in time complexity. To strike this fundamental tradeoff, we formulate the maximum likelihood detection as a binary optimization problem and solve it via the Grover adaptive search (GAS), a quantum exhaustive search algorithm offering quadratic speedup. We further introduce a search space reduction technique using quantum W states and controlled-H gates, which substantially decreases complexity. In addition, we investigate the effects of efficient parameter settings in GAS. Our simulation results show that the proposed detector achieved the optimal detection performance while reducing the query complexity, thereby highlighting its potential as a solution for future quantum-accelerated overloaded MIMO systems.

IEEE Vehicular Technology Conference•Oct 19, 2025•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
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 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.
In this paper, we address the joint maximum-likelihood detection of power-domain non-orthogonal multiple access and transform the detection problem into a binary optimization problem. Then, we solve it by a quantum algorithm, Grover adaptive search (GAS), and further accelerate the algorithm. Assuming fault-tolerant quantum computing, GAS provides a quadratic speedup for binary optimization problems in terms of query complexity. The proposed method designs the number of Grover operators using a time-invariant distribution of the number of solutions, which can be obtained in advance. Simulation results demonstrate that the proposed method is capable of reducing the query complexity in the classical domain while achieving the optimal performance.
In this paper, we propose a quantum-native formulation of maximum likelihood detection (MLD) for overloaded multiple-input multiple-output (MIMO) systems in a random access channel, where numerous user terminals share the same channel resource and asynchronously transmit signals. Classical linear detectors suffer from significant performance degradation in this scenario, whereas the exhaustive-search MLD achieves the optimal performance but incurs an exponential computational complexity. To overcome this trade-off, we formulate the MLD as a binary optimization problem and solve it via Grover adaptive search (GAS) -- a quantum exhaustive search algorithm offering quadratic speedup in fault-tolerant quantum computing. We then introduce a search space reduction technique to substantially decrease the required computational resources. In addition, we investigate efficient parameter settings for GAS through probability analysis to improve convergence performance. We demonstrate that the proposed detector achieves the optimal detection performance while reducing the required Grover rotation count to reach the solution by up to approximately 65% compared with the conventional GAS, showing its potential as a viable solution for future quantum-accelerated wireless systems.
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.
In this paper, we propose a quantum-native formulation of maximum likelihood detection in random access channel with overloaded multiple-input multiple-output (MIMO), where a number of user terminals share the same channel resource and asynchronously transmit signals. Classical low-complexity linear detectors suffer from significant performance degradation in this scenario, while the exhaustive-search-based maximum likelihood detection achieves the optimal performance but induces an exponential increase in time complexity. To strike this fundamental tradeoff, we formulate the maximum likelihood detection as a binary optimization problem and solve it via the Grover adaptive search (GAS), a quantum exhaustive search algorithm offering quadratic speedup. We further introduce a search space reduction technique using quantum W states and controlled-H gates, which substantially decreases complexity. In addition, we investigate the effects of efficient parameter settings in GAS. Our simulation results show that the proposed detector achieved the optimal detection performance while reducing the query complexity, thereby highlighting its potential as a solution for future quantum-accelerated overloaded MIMO systems.
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.