Classical computing still suffers from the high computational complexity of finding the extreme value of a constrained goal function or an unordered database with respect to a certain constraint. Quantum computing offers new possibilities and solutions due to its quantum nature to surmount this problem. In this paper, we extended a new version of quantum existence testing (QET) _we call it a constrained quantum relation testing (CQRT)_ we also investigate analytically its classical and quantum certainty. Furthermore, we show how the CQRT can be applied for extending the quantum extreme value searching algorithm (QEVSA) version to a constrained quantum optimization algorithm (CQOA). And we gave an extensive explanation of how the CQOA works and how it finds the extreme constrained optimum value solution with high complexity reduction, maximum exponential speed, and high certainty.
Classical computing still suffers from the high computational complexity of finding the extreme value of a constrained goal function or an unordered database with respect to a certain constraint. Quantum computing offers new possibilities and solutions due to its quantum nature to surmount this problem. In this paper, we extended a new version of quantum existence testing (QET) we call it a constrained quantum relation testing (CQRT) we also investigate analytically its classical and quantum certainty. Furthermore, we show how the CQRT can be applied for extending the quantum extreme value searching algorithm (QEVSA) version to a constrained quantum optimization algorithm (CQOA). And we gave an extensive explanation of how the CQOA works and how it finds the extreme constrained optimum value solution with high complexity reduction, maximum exponential speed, and high certainty.
Quantum computing appears as an alternative solution for solving computationally intractable problems. This paper presents a new constrained quantum genetic algorithm designed specifically for identifying the extreme value of a highly constrained optimization problem, where the search space size _database is massive and unsorted_ cannot be handled by the currently available classical or quantum processor, called the highly constrained quantum genetic algorithm (HCQGA). To validate the efficiency of the suggested quantum method, maximizing the energy efficiency with respect to the target user bit rate of an uplink multi-cell massive multiple-input and multiple- output (MIMO) system is considered as an application. Simulation results demonstrate that the proposed HCQGA converges rapidly to the optimum solution compared with its classical benchmark.
Many information processing and computing problems can be traced back to find the extreme value of a database or a function. Unfortunately, classical solutions suffer from high computational complexity if the database is unsorted or, equivalently, the function has many local minimum/maximum points. Proposed quantum computing-based solutions involve the repeated application of Grower's searching algorithm. In this paper, we introduce a new technique exploiting the parallel processing capabilities of quantum computing in a different way. We derive a special case of quantum counting - we call it quantum existence testing - which allows adapting the classical logarithmic search algorithm so that it is suitable for structured databases to unstructured ones. The paper analyzes the required number of database queries, the corresponding computational complexity, and the probability of error and their relationship
In the past decades, many quantum algorithms have been developed. The main obstacle that prevents the widespread implementation of these algorithms is the small size of the available quantum computer in terms of qubits. Blind Quantum Computation (BQC) holds the promise of handling this issue by delegating computation to quantum remote devices. Here, we introduce a novel Constrained Quantum Genetic Algorithm (CQGA) that selects the optimum extreme (minimum or maximum) value of a constrained goal function (or a vast unsorted database) with very low computational complexity. Since the convergence speed to the optimal solution for the Constrained Classical Genetic Algorithm (CCGA) is highly dependent on the level of quality of the initially selected potential solutions, the CCGA's heuristic initialization stage is replaced by a quantum one. This is achieved by exploiting the strengths of the Constrained Quantum Optimization Algorithm (CQOA) and the BQC. The proposed CQGA is applied as an embedded computational infrastructure for the uplink multi-cell massive MIMO system. The algorithm maximizes the energy efficiency (EE) of the uplink massive MIMO while considering different users target bit rate classes. Simulation results show that the suggested CQGA maximizes energy efficiency through careful computation of the optimal transmit power for each active user using fewer computational steps than the CCGA. We demonstrated that when the overall transmit power set or the overall number of active users increases, the CQGA keeps executing a smaller number of generation steps compared to the CCGA. For instance, if we consider a scenario where the overall number of active users () is set to 18, the CQGA finds the optimal solution with a smaller number of generation steps equal to 6, while the CCGA takes a larger number of generation steps, reaching 65.
Considerable effort has been made recently in the development of heuristic quantum algorithms for solving combinatorial optimization problems. Meanwhile, these problems have been studied extensively in classical computing for decades. In this paper, we explore a natural approach to leveraging existing classical techniques to enhance quantum optimization. Specifically, we run a classical algorithm to find an approximate solution and then use a quantum circuit to search its "neighborhood" for higher-quality solutions. We propose the Classically-Boosted Quantum Optimization Algorithm (CBQOA) that is based on this idea and can solve a wide range of combinatorial optimization problems, including all unconstrained problems and many important constrained problems such as Max Bisection, Maximum Independent Set, Minimum Vertex Cover, Portfolio Optimization, Traveling Salesperson and so on. A crucial component of this algorithm is an efficiently-implementable continuous-time quantum walk (CTQW) on a properly-constructed graph that connects the feasible solutions. CBQOA utilizes this CTQW and the output of an efficient classical procedure to create a suitable superposition of the feasible solutions which is then processed in certain way. This algorithm has the merits that it solves constrained problems without modifying their cost functions, confines the evolution of the quantum state to the feasible subspace, and does not rely on efficient indexing of the feasible solutions. We demonstrate the applications of CBQOA to Max 3SAT and Max Bisection, and provide empirical evidence that it outperforms previous approaches on these problems.
Combinatorial optimization problems that arise in science and industry typically have constraints. Yet the presence of constraints makes them challenging to tackle using both classical and quantum optimization algorithms. We propose a new quantum algorithm for constrained optimization, which we call quantum constrained Hamiltonian optimization (Q-CHOP). Our algorithm leverages the observation that for many problems, while the best solution is difficult to find, the worst feasible (constraint-satisfying) solution is known. The basic idea of Q-CHOP is to enforce a Hamiltonian constraint at all times, thereby restricting evolution to the subspace of feasible states, and slowly “rotate” an objective Hamiltonian to trace an adiabatic path from the worst feasible state to the best feasible state. Q-CHOP thereby assigns qualitatively distinct roles to the constraint and objective functions of a constrained optimization problem. We additionally propose a version of Q-CHOP that can start in any feasible state. Finally, we benchmark Q-CHOP against the commonly-used adiabatic algorithm of quantum annealing with an objective function that penalizes constraint violation, and find that Q-CHOP consistently performs significantly better on a wide range of problems, including textbook graph problems, knapsack problems, combinatorial auctions, and a real-world financial use case of bond exchange-traded fund basket optimization.
While the development of quantum computers promises a myriad of advantages over their classical counterparts, care must be taken when designing algorithms that substitute a classical technique with a potentially advantageous quantum method. The probabilistic nature of many quantum algorithms may result in new behavior that could negatively impact the performance of the larger algorithm. The purpose of this work is to preserve the advantages of applying quantum search methods for generalized pattern search algorithms (GPSs) without violating the convergence criteria. It is well known that quantum search methods are able to reduce the expected number of oracle calls needed for finding the solution to a search problem from O(N) to O(N) However, the number of oracle calls needed to determine that no solution exists with certainty is exceedingly high and potentially infinite. In the case of GPS, this is a significant problem since overlooking a solution during an iteration will violate a needed assumption for convergence. Here, we overcome this problem by introducing the quantum improved point search (QIPS), a classical–quantum hybrid variant of the quantum search algorithm QSearch. QIPS retains the O(N) oracle query complexity of QSearch when a solution exists. However, it is able to determine when no solution exists, with certainty, using only O(N) oracle calls.