Abstract A binary constant weight code is a type of error-correcting code with a wide range of applications. The problem of finding a binary constant weight code has long been studied as a combinatorial optimization problem in coding theory. In this paper, we propose a quantum search algorithm for binary constant weight codes. Specifically, the search problem is formulated as a polynomial binary optimization problem and Grover adaptive search is used for providing the quadratic speedup. Focusing on the inherent structure of the problem, we derive an upper bound on the minimum of the objective function value and a lower bound on the exact number of solutions. By exploiting these two bounds, we successfully reduced the constant overhead of the algorithm, although the overall query complexity remains exponential due to the NP-complete nature of the problem. In our algebraic analysis, it was found that this proposed algorithm is capable of reducing the number of required qubits, thus enhancing the feasibility. Additionally, our simulations demonstrated that it reduces the average number of classical iterations by 63% as well as the average number of total Grover rotations by 31%. The proposed approach may be useful for other quantum search algorithms and optimization problems.
Abstract A binary constant weight code is a type of error-correcting code with a wide range of applications. The problem of finding a binary constant weight code has long been studied as a combinatorial optimization problem in coding theory. In this paper, we propose a quantum search algorithm for binary constant weight codes. Specifically, the search problem is formulated as a polynomial binary optimization problem and Grover adaptive search is used for providing the quadratic speedup. Focusing on the inherent structure of the problem, we derive an upper bound on the minimum of the objective function value and a lower bound on the exact number of solutions. By exploiting these two bounds, we successfully reduced the constant overhead of the algorithm, although the overall query complexity remains exponential due to the NP-complete nature of the problem. In our algebraic analysis, it was found that this proposed algorithm is capable of reducing the number of required qubits, thus enhancing the feasibility. Additionally, our simulations demonstrated that it reduces the average number of classical iterations by 63% as well as the average number of total Grover rotations by 31%. The proposed approach may be useful for other quantum search algorithms and optimization problems.
In binary optimization problems, where the goal is to find the inputxthat 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.
The weight decision problem, which requires to determine the Hamming weight of a given binary string, is a natural and important problem, with applications in cryptanalysis, coding theory, fault-tolerant circuit design and so on. In particular, both Deutsch-Jozsa problem and Grover search problem can be interpreted as special cases of weight decision problems. In this work, we investigate the exact quantum query complexity of weight decision problems, where the quantum algorithm must always output the correct answer. More specifically we consider a partial Boolean function which distinguishes whether the Hamming weight of the length-n input is k or it is l. Our contribution includes both upper bounds and lower bounds for the precise number of queries. Furthermore, for most choices of (nk,nl) and sufficiently large n, the gap between our upper and lower bounds is no more than one. To get the results, we first build the connection between Chebyshev polynomials and our problem, then determine all the boundary cases of (nk,nl) with matching upper and lower bounds, and finally we generalize to other cases via a new \emph{quantum padding} technique. This quantum padding technique can be of independent interest in designing other quantum algorithms.
Abstract Graph coloring with minimum colors is a well-known NP-complete problem in computer science and mathematics, having diverse real-life applications such as scheduling, register allocation, and frequency assignment. However, a classical computer requires exponential time to solve the graph coloring problem with the minimum number of colors. Therefore, classical approaches become infeasible for solving this problem on large graphs. In contrast, quantum computing offers the potential for speedup on specific problems, although solutions are typically obtained with a certain probability of correctness. This work proposes a quantum–classical method for solving the graph coloring problem and finding the chromatic number of a graph with guaranteed correctness, and also reduces the time and qubit complexities. The proposed method is inspired by Randomized Grover’s search algorithm, and the classical binary search algorithm. Here, Randomized Grover’s search algorithm provides quadratic speedup and this algorithm is useful in real situations when the number of solutions is not known in advance in contrast to the Grover’s search algorithm. The binary search algorithm helps to achieve logarithmic speedup, which reduces overall complexity. The experimental results strongly validate our claims and demonstrate the superiority of the approach. Furthermore, a comprehensive mathematical analysis is carried out to examine its complexities, as well as to compare its computational efficiency with existing methods.
In this paper we discuss Grover Adaptive Search (GAS) for Constrained Polynomial Binary Optimization (CPBO) problems, and in particular, Quadratic Unconstrained Binary Optimization (QUBO) problems, as a special case. GAS can provide a quadratic speed-up for combinatorial optimization problems compared to brute force search. However, this requires the development of efficient oracles to represent problems and flag states that satisfy certain search criteria. In general, this can be achieved using quantum arithmetic, however, this is expensive in terms of Toffoli gates as well as required ancilla qubits, which can be prohibitive in the near-term. Within this work, we develop a way to construct efficient oracles to solve CPBO problems using GAS algorithms. We demonstrate this approach and the potential speed-up for the portfolio optimization problem, i.e. a QUBO, using simulation and experimental results obtained on real quantum hardware. However, our approach applies to higher-degree polynomial objective functions as well as constrained optimization problems.
Cardinality-constrained binary optimization is a fundamental computational primitive with broad applications in machine learning, finance, and scientific computing. In this work, we introduce a Grover-based quantum algorithm that exploits the structure of the fixed-cardinality feasible subspace under a natural promise on solution existence. For quadratic objectives, our approach achieves O(M(kn)) Grover rotations for any fixed cardinality k and degeneracy of the optima M, yielding an exponential reduction in the number of Grover iterations compared with unstructured search over {0,1}n. Building on this result, we develop a hybrid classical--quantum framework based on the alternating direction method of multipliers (ADMM) algorithm. The proposed framework is guaranteed to output an ε-approximate solution with a consistency tolerance ε+δ using at most $ {O}\left(\sqrt{\binom{n}{k}}\frac{n^{6}k^{3/2} }{ \sqrt{M}ε^2 δ}\right)$ queries to a quadratic oracle, together with O(ε2δn6k3/2) classical overhead. Overall, our method suggests a practical use of quantum resources and demonstrates an exponential improvements over existing Grover-based approaches in certain parameter regimes, thereby paving the way toward quantum advantage in constrained binary optimization.
This paper presents a novel approach to Grover adaptive search (GAS) for a combinatorial optimization problem whose objective function involves spin variables. While the GAS algorithm with a conventional design of a quantum dictionary subroutine handles a problem associated with an objective function with binary variables{0,1}, we reformulate the problem using spin variables{+1,−1}to simplify the algorithm. Specifically, we introduce a novel quantum dictionary subroutine that is designed for this spin-based formulation. A key benefit of this approach is the substantial reduction in the number of CNOT gates required to construct the quantum circuit. We theoretically demonstrate that, for certain problems, our proposed approach can reduce the gate complexity from an exponential order to a polynomial order, compared to the conventional binary-based approach. This improvement has the potential to enhance the scalability and efficiency of GAS, particularly in larger quantum computations.