The computational capabilities of near-term quantum computers are limited by the noisy execution of gate operations and a limited number of physical qubits. Hybrid variational algorithms are well-suited to near-term quantum devices because they allow for a wide range of tradeoffs between the amount of quantum and classical resources used to solve a problem. This paper investigates tradeoffs available at both the algorithmic and hardware levels by studying a specific case – applying the Quantum Approximate Optimization Algorithm (QAOA) to instances of the Maximum Independent Set (MIS) problem. We consider three variants of the QAOA which offer different tradeoffs at the algorithmic level in terms of their required number of classical parameters, quantum gates, and iterations of classical optimization needed. Since MIS is a constrained combinatorial optimization problem, the QAOA must respect the problem constraints. This can be accomplished by using many multi-controlled gate operations which must be decomposed into gates executable by the target hardware. We study the tradeoffs available at this hardware level, combining the gate fidelities and decomposition efficiencies of different native gate sets into a single metric called the gate decomposition cost .
The computational capabilities of near-term quantum computers are limited by the noisy execution of gate operations and a limited number of physical qubits. Hybrid variational algorithms are well-suited to near-term quantum devices because they allow for a wide range of tradeoffs between the amount of quantum and classical resources used to solve a problem. This paper investigates tradeoffs available at both the algorithmic and hardware levels by studying a specific case – applying the Quantum Approximate Optimization Algorithm (QAOA) to instances of the Maximum Independent Set (MIS) problem. We consider three variants of the QAOA which offer different tradeoffs at the algorithmic level in terms of their required number of classical parameters, quantum gates, and iterations of classical optimization needed. Since MIS is a constrained combinatorial optimization problem, the QAOA must respect the problem constraints. This can be accomplished by using many multi-controlled gate operations which must be decomposed into gates executable by the target hardware. We study the tradeoffs available at this hardware level, combining the gate fidelities and decomposition efficiencies of different native gate sets into a single metric called the gate decomposition cost .
Quantum approximate optimization algorithm (QAOA) is a promising quantum-classical hybrid technique to solve NP-hard problems in near-term gate-based noisy quantum devices. In QAOA, the gate parameters of a parameterized quantum circuit (PQC) are varied by a classical optimizer to generate a quantum state with a significant support to the optimal solution. The existing analysis fails to consider nonidealities in the qubit quality i.e., short lifetime and imperfect gate operations in a realistic quantum hardware. In this article, we study the impact of various noise sources on the performance of QAOA both in simulation and on a real quantum computer from IBM. Our analysis indicates that QAOA performance is noise-sensitive (especially higher-depth QAOA instances). Therefore, the optimal number of stages (p-value) for any QAOA instance is limited by the noise in the target hardware as opposed to the current perception that QAOA will provide monotonically better performance with higher-depth. We show that the two-qubit gate error has to be decreased by more than 75% of the current state-of-the-art levels to attain a performance within 10% of the maximum value for the lowest-depth QAOA.
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.
Variational quantum algorithms are believed to be promising for solving computationally hard problems and are often comprised of repeated layers of quantum gates. An example thereof is the quantum approximate optimization algorithm (QAOA), an approach to solve combinatorial optimization problems on noisy intermediate-scale quantum (NISQ) systems. Gaining computational power from QAOA critically relies on the mitigation of errors during the execution of the algorithm, which for coherence-limited operations is achievable by reducing the gate count. Here, we demonstrate an improvement of up to a factor of 3 in algorithmic performance as measured by the success probability, by implementing a continuous hardware-efficient gate set using superconducting quantum circuits. This gate set allows us to perform the phase separation step in QAOA with a single physical gate for each pair of qubits instead of decomposing it into two CZ-gates and single-qubit gates. With this reduced number of physical gates, which scales with the number of layers employed in the algorithm, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances mapped onto three and seven qubits, using up to a total of 399 operations and up to 9 layers. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
Quantum algorithms have been widely studied in the context of combinatorial optimization problems. While this endeavor can often analytically and practically achieve quadratic speedups, theoretical and numeric studies remain limited, especially compared to the study of classical algorithms. We propose and study an alternative class of hybrid approaches to quantum optimization, termed iterative quantum algorithms, which in particular generalizes the recursive quantum approximate optimization algorithm (QAOA). This paradigm can incorporate hard problem constraints, which we demonstrate by considering the maximum independent set (MIS) problem. We show that, for QAOA with p=1 circuit layers, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS. We then turn to deeper p>1 circuits and other ways to modify the quantum algorithm that can no longer be easily mimicked by classical algorithms, and empirically confirm improved performance. Our work demonstrates the practical importance of incorporating proven classical techniques into more effective hybrid quantum-classical algorithms.
Universal fault-tolerant quantum computers will require error-free execution of long sequences of quantum gate operations, which is expected to involve millions of physical qubits. Before the full power of such machines will be available, near-term quantum devices will provide several hundred qubits and limited error correction. Still, there is a realistic prospect to run useful algorithms within the limited circuit depth of such devices. Particularly promising are optimization algorithms that follow a hybrid approach: the aim is to steer a highly entangled state on a quantum system to a target state that minimizes a cost function via variation of some gate parameters. This variational approach can be used both for classical optimization problems as well as for problems in quantum chemistry. The challenge is to converge to the target state given the limited coherence time and connectivity of the qubits. In this context, the quantum volume as a metric to compare the power of near-term quantum devices is discussed. With focus on chemistry applications, a general description of variational algorithms is provided and the mapping from fermions to qubits is explained. Coupled-cluster and heuristic trial wave-functions are considered for efficiently finding molecular ground states. Furthermore, simple error-mitigation schemes are introduced that could improve the accuracy of determining ground-state energies. Advancing these techniques may lead to near-term demonstrations of useful quantum computation with systems containing several hundred qubits.
This dissertation addresses fundamental challenges in solving constrained combinatorial optimization problems using hybrid quantum-classical computing approaches. Quantum computing shows promise for tackling computationally intractable problems, current approaches face significant limitations. The path forward in computing involves combining quantum and classical computing approaches. Quantum processing units (QPUs) will play a key role in accelerating algorithms in optimization, simulation, and machine learning applications beyond what classical computers can achieve on their own, similar to how graphical processing units (GPUs) have become integral to general-purpose computing. The current generation of quantum devices is limited by noise and circuit depth constraints, making it challenging to gain practical utility. Hybrid quantum-classical approaches, which combine quantum computing resources with classical computing resources, are essential for addressing these limitations on near-term devices. In the area of combinatorial optimization, current practical state-of-the-art hybrid approaches are variational in nature, relying on parameterized quantum circuits to encode solutions and classical optimization techniques to find optimal parameters. While the ultimate goal of solving computationally intractable problems is to find provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). QAOA alternates between two operators: a problem-specific cost Hamiltonian that encodes the optimization objective, and a mixer Hamiltonian that explores the solution space. The algorithm's parameters are iteratively optimized using classical methods to maximize the probability of sampling high-quality solutions. However, these methods often struggle with solution feasibility, especially for problems where the solutions must satisfy specific constraints. Penalty-based encodings require careful parameter tuning and risk producing infeasible solutions, while feasibility-preserving methods demand deeper quantum circuits that are challenging to implement on near-term quantum devices. In this dissertation, we present novel strategies that reduce or omit dependency on penalty parameters while maintaining solution quality, effectively capturing both optimal and near-optimal solutions, and balancing the trade-offs between circuit depth and solution feasibility. We present SCOOP, a novel QAOA-based framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. QAOA operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the effectiveness of the SCOOP framework on selected NP-hard problems, some of which can be encoded quadratically (such as Minimum Vertex Cover and Maximum Independent Set), and some that can be encoded using higher-order terms (such as Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover). We also apply our framework to constrained combinatorial optimization problems that can be solved in polynomial time, such as Minimum Edge Cover and Maximum Matching. Experimental results on full statevector simulators and tensor network simulators show that SCOOP significantly improves the probability of finding high-quality feasible solutions across various problem classes, on problems that can be encoded quadratically as well as problems that can be encoded using higher-order terms. We also demonstrate the effectiveness of SCOOP on real quantum hardware, specifically IBM Quantum Heron R2 processors with 156 qubits, showing that SCOOP can be applied to practical problems with current quantum hardware limitations. This work makes significant contributions toward achieving quantum utility by enabling systematic investigation of constrained optimization problems on quantum devices. While current quantum computing research primarily focuses on unconstrained problems like MaxCut, real-world applications typically involve constraints. SCOOP provides a scalable framework for encoding constrained problems, extending quantum computing's practical utility beyond simple unconstrained cases. By eliminating dependency on penalty parameters and providing natural problem formulations, SCOOP makes it feasible to explore quantum solutions for constrained problems where classical exact methods become intractable. This capability is crucial for identifying promising avenues for demonstrating quantum utility across diverse constrained optimization problems, advancing the practical applicability of quantum computing approaches.