© 2026 Aqora Quantum S.A.S.

Terms Privacy Legal Notice

arXiv:2406.07187 · IEEE Transactions on Quantum Engineering

Quantum Speedup of the Dispersion and Codebook Design Problems

Kein Yukiyoshi, Taku Mikuriya, Hyeon Seok Rou, Giuseppe Thadeu Freitas de Abreu, Naoki Ishikawa

Published Jan 1, 2024• 12 citations

Abstract

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.

DOI: 10.1109/tqe.2024.3450852

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

Quantum Speedup for Multiuser Detection With Optimized Parameters in Grover Adaptive Search

Masaya Norimoto, Taku Mikuriya, Naoki Ishikawa

Maximum-likelihood multiuser detection incurs a large computational complexity, and its low-complexity detection scheme suffers from a performance loss, where this tradeoff is inevitable and inherent in a classical computer. In this paper, we use the Grover adaptive search (GAS) to break the tradeoff, which is a quantum exhaustive search algorithm guaranteed to obtain the optimal solution, achieving a quadratic speedup. Specifically, we design two specific parameters of GAS to achieve the optimal performance with a reduced complexity: the initial threshold and the number of Grover rotations. The initial threshold of GAS can be optimized using a solution of semi-definite programming, and it is possible to calculate the distribution of the number of solutions smaller than the initial threshold in advance, which depends on instantaneous channel coefficients. In addition, we analyze the number of quantum gates required for GAS and show that the gate count can be reduced by bypassing the higher-order terms in the objective function, leading to a reduced circuit runtime. Our analysis and simulation results demonstrate that the proposed approach achieves the same performance as the optimal maximum-likelihood detection while reducing the query complexity of GAS, implying that the large constant overhead of quadratic speedup can be further reduced.

IEEE Access•Jan 1, 2024•6 citations

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

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

Grover Adaptive Search With Fewer Queries

Hiroaki Ominato, Takahiro Ohyama, Koichiro Yamaguchi

In binary optimization problems, where the goal is to find the input$\boldsymbol {x}$that minimizes a given objective function, Grover adaptive search (GAS) is a well-known quantum algorithm that provides quadratic speedup when compared with the brute-force approaches of classical computers. GAS calls a renowned quantum search algorithm, Grover search (GS), as a subroutine to search for inputs with function values less than the threshold value. If such an input is found, the threshold value is updated with the function value and the search targets are narrowed. To search efficiently for a solution, an appropriate number of queries must be selected to amplify the desired state of the GS in each step. This paper discusses this issue and proposes a new method for selecting the number of queries and provides proof that our method achieves quadratic speedup as well as the original GAS. Furthermore, the simulation results for 40-bit problems confirm that our method allows an optimal solution with 22% fewer queries than the standard method, thus offering the possibility of significantly reduced computation times for combinatorial optimization problems.

IEEE Access•Jan 1, 2024•4 citations

Quantum Speedup for Pilot Assignment Problems

Taku Mikuriya, Kengo Ando, Kein Yukiyoshi +3 more

We propose a quantum-assisted solution of the pilot assignment problem. In particular, we formulate a pilot assignment problem designed to minimize the interference from co-pilot user terminals as a binary optimization problem which can be solved via a quantum exhaustive search through the Grover adaptive search (GAS) algorithm. The performance of GAS in terms of query complexity is enhanced by introducing a modified initial state and an improved initial threshold using the upper bound for the minimum value of the objective function. Simulation results demonstrate that our proposed method can provide quadratic speedup compared to an exhaustive search performed by a classical computer, concretely demonstrating that quantum computers can be employed to solve optimally and efficiently the pilot assignment problem.

IEEE Vehicular Technology Conference•Jun 17, 2025•0 citations

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.

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.

Maximum-likelihood multiuser detection incurs a large computational complexity, and its low-complexity detection scheme suffers from a performance loss, where this tradeoff is inevitable and inherent in a classical computer. In this paper, we use the Grover adaptive search (GAS) to break the tradeoff, which is a quantum exhaustive search algorithm guaranteed to obtain the optimal solution, achieving a quadratic speedup. Specifically, we design two specific parameters of GAS to achieve the optimal performance with a reduced complexity: the initial threshold and the number of Grover rotations. The initial threshold of GAS can be optimized using a solution of semi-definite programming, and it is possible to calculate the distribution of the number of solutions smaller than the initial threshold in advance, which depends on instantaneous channel coefficients. In addition, we analyze the number of quantum gates required for GAS and show that the gate count can be reduced by bypassing the higher-order terms in the objective function, leading to a reduced circuit runtime. Our analysis and simulation results demonstrate that the proposed approach achieves the same performance as the optimal maximum-likelihood detection while reducing the query complexity of GAS, implying that the large constant overhead of quadratic speedup can be further reduced.

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.

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.

In binary optimization problems, where the goal is to find the input

\boldsymbol {x}

that minimizes a given objective function, Grover adaptive search (GAS) is a well-known quantum algorithm that provides quadratic speedup when compared with the brute-force approaches of classical computers. GAS calls a renowned quantum search algorithm, Grover search (GS), as a subroutine to search for inputs with function values less than the threshold value. If such an input is found, the threshold value is updated with the function value and the search targets are narrowed. To search efficiently for a solution, an appropriate number of queries must be selected to amplify the desired state of the GS in each step. This paper discusses this issue and proposes a new method for selecting the number of queries and provides proof that our method achieves quadratic speedup as well as the original GAS. Furthermore, the simulation results for 40-bit problems confirm that our method allows an optimal solution with 22% fewer queries than the standard method, thus offering the possibility of significantly reduced computation times for combinatorial optimization problems.

We propose a quantum-assisted solution of the pilot assignment problem. In particular, we formulate a pilot assignment problem designed to minimize the interference from co-pilot user terminals as a binary optimization problem which can be solved via a quantum exhaustive search through the Grover adaptive search (GAS) algorithm. The performance of GAS in terms of query complexity is enhanced by introducing a modified initial state and an improved initial threshold using the upper bound for the minimum value of the objective function. Simulation results demonstrate that our proposed method can provide quadratic speedup compared to an exhaustive search performed by a classical computer, concretely demonstrating that quantum computers can be employed to solve optimally and efficiently the pilot assignment problem.