This article investigates the performance impact of five classical optimization approximation algorithms on our previously introduced quantum search algorithm, termed the Boolean–Hamiltonians Transform for Quantum Approximate Optimization Algorithm (BHT-QAOA), to effectively search for all best-approximated solutions for Boolean-based problems. These optimization approximation algorithms are BFGS, L-BFGS-B, SLSQP, COBYLA, and COBYQA. Their performance impact is evaluated and compared using two proposed performance metrics—(i) the final number of function evaluations (the lower numbers denote the best optimization approximation algorithms) and (ii) the final quality of qubit measurements (the higher values indicate all best-approximated solutions were found for a problem). Arbitrary classical Boolean problems in various logical structures were examined and evaluated using the BHT-QAOA, these five optimization approximation algorithms, and a simulated noisy model of an IBM quantum computer. Broadly, the BHT-QAOA, with these five algorithms, successfully finds all optimized approximated solutions for these problems. Specifically, both the BFGS and SLSQP algorithms successfully find all best-approximated solutions for these problems, in the context of fewer function evaluations and higher quality of qubit measurements.
This article investigates the performance impact of five classical optimization approximation algorithms on our previously introduced quantum search algorithm, termed the Boolean–Hamiltonians Transform for Quantum Approximate Optimization Algorithm (BHT-QAOA), to effectively search for all best-approximated solutions for Boolean-based problems. These optimization approximation algorithms are BFGS, L-BFGS-B, SLSQP, COBYLA, and COBYQA. Their performance impact is evaluated and compared using two proposed performance metrics—(i) the final number of function evaluations (the lower numbers denote the best optimization approximation algorithms) and (ii) the final quality of qubit measurements (the higher values indicate all best-approximated solutions were found for a problem). Arbitrary classical Boolean problems in various logical structures were examined and evaluated using the BHT-QAOA, these five optimization approximation algorithms, and a simulated noisy model of an IBM quantum computer. Broadly, the BHT-QAOA, with these five algorithms, successfully finds all optimized approximated solutions for these problems. Specifically, both the BFGS and SLSQP algorithms successfully find all best-approximated solutions for these problems, in the context of fewer function evaluations and higher quality of qubit measurements.
A new methodology is introduced to solve classical Boolean problems as Hamiltonians, using the quantum approximate optimization algorithm (QAOA). This methodology is termed the "Boolean-Hamiltonians Transform for QAOA" (BHT-QAOA). Because a great deal of research and studies are mainly focused on solving combinatorial optimization problems using QAOA, the BHT-QAOA adds an additional capability to QAOA to find all optimized approximated solutions for Boolean problems, by transforming such problems from Boolean oracles (in different structures) into Phase oracles, and then into the Hamiltonians of QAOA. From such a transformation, we noticed that the total utilized numbers of qubits and quantum gates are dramatically minimized for the generated Hamiltonians of QAOA. In this article, arbitrary Boolean problems are examined by successfully solving them with our BHT-QAOA, using different structures based on various logic synthesis methods, an IBM quantum computer, and a classical optimization minimizer. Accordingly, the BHT-QAOA will provide broad opportunities to solve many classical Boolean-based problems as Hamiltonians, for the practical engineering applications of several algorithms, digital synthesizers, robotics, and machine learning, just to name a few, in the hybrid classical-quantum domain.
A new methodology is proposed to solve classical Boolean problems as Hamiltonians, using the quantum approximate optimization algorithm (QAOA). Our methodology successfully finds all optimized approximated solutions for Boolean problems, after converting them from Boolean oracles (in different structures) into Phase oracles, and then into the Hamiltonians of QAOA. From such a conversion, we noticed that the total utilized numbers of qubits and quantum gates are dramatically minimized for the final quantum circuits of Hamiltonians. In this paper, arbitrary classical Boolean problems are examined by successfully solving them with our proposed methodology, using structures based on various logic synthesis methods, an IBM quantum computer, and a classical optimization minimizer. Accordingly, this methodology will provide broad opportunities to solve many classical Boolean problems as Hamiltonians, for the practical engineering applications of several algorithms, robotics, machine learning, just to name a few, in the hybrid classical-quantum domain.
The BHT-QAOA is a hybrid classical-quantum algorithm that solves arbitrary classical Boolean problems as Hamiltonians in the quantum domain, using the quantum approximate optimization algorithm (QAOA) [1]. The BHT-QAOA stands for the "Boolean-Hamiltonians Transform for QAOA" [2]. Research and studies are mainly focused on solving combinatorial optimization problems using QAOA, e.g., the MaxCut problem [1]. However, the BHT-QAOA adds an additional capability to QAOA to find all optimized approximated solutions for classical Boolean problems, as expressed in the following steps and demonstrated in the figure below. Design classical Boolean problems into quantum Boolean oracles in different logical structures, such as POS, SOP, ESOP, CSP-SAT, XOR-SAT, just to name a few. Convert these quantum Boolean oracles into quantum Phase oracles. Transform these quantum Phase oracles into the Hamiltonians (HC and HM) of QAOA. Please observe that, from the aforementioned steps, the total utilized numbers of qubits and quantum gates are significantly reduced for the final generated Hamiltonians (HC and HM) of QAOA. Accordingly, the BHT-QAOA will provide broad opportunities to solve many classical Boolean-based problems as Hamiltonians, for the practical engineering applications of several algorithms, digital synthesizers, robotics, machine learning, just to name a few, in the hybrid classical-quantum domain.
The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm to solve binary-variable optimization problems. Due to its expected robustness to systematic errors and the short circuit depth, it is one of the promising candidates likely to run on near-term quantum devices. We project the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives, both for exact or approximate solution. When comparing approximate solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we introduce performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. By selecting a suitable optimizer for the variational parameters and reducing the number of function evaluations, QAOA performance improves by up to 2 orders of magnitude compared to previous estimates. Especially for 3-regular random graphs, this setting decreases the performance gap with classical alternatives.
Abstract The quantum approximate optimization algorithm (QAOA) is a hybrid quantum–classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors it is a promising candidate likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. In particular for three-regular random graphs, QAOA performance shows improvement by up to two orders of magnitude compared to previous estimates, strongly reducing the performance gap with classical alternatives. This was possible by reducing the number of function evaluations per iteration and optimizing the variational parameters on small graph instances and transferring to large via training. Because QAOA’s performance guarantees are only known for limited applications and contexts, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.
The quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve combinatorial optimization problems in near-term gate-based noisy quantum devices. In QAOA, the objective is a function of the quantum state, which itself is a function of the gate parameters of a multi-level parameterized quantum circuit (PQC). A classical optimizer varies the continuous gate parameters to generate distributions (quantum state) with significant support to the optimal solution. Even at the lowest circuit depth, QAOA offers non-trivial provable performance guarantee which is expected to increase with the circuit depth. However, the existing analysis fails to consider non-idealities in the qubit quality i.e., short lifetime and imperfect gate operations in realistic quantum hardware. In this article, we investigate the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analyses indicate that the optimal number of stages (p-value) for any QAOA instance is limited by the noise characteristics (gate error, coherence time, etc.) of the target hardware as opposed to the current perception that higher-depth QAOA will provide monotonically better performance for a given problem compared to the low-depth implementations.