Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Design and Optimization in Near-term Quantum Computation

Aniruddha Bapat

Published Jan 1, 2021• 0 citations
Publisher

Abstract

Quantum computers have come a long way since conception, and there is still a long way to go before the dream of universal, fault-tolerant computation is realized. In the near term, quantum computers will occupy a middle ground that is popularly known as the “Noisy, Intermediate-Scale Quantum” (or NISQ) regime. The NISQ era represents a transition in the nature of quantum devices from experimental to computational. There is significant interest in engineering NISQ devices and NISQ algorithms in a manner that will guide the development of quantum computation in this regime and into the era of fault-tolerant quantum computing. In this thesis, we study two aspects of near-term quantum computation. The first of these is the design of device architectures, covered in Chapters 2, 3, and 4. We examine different qubit connectivities on the basis of their graph properties, and present numerical and analytical results on the speed at which large entangled states can be created on nearest-neighbor grids and graphs with modular structure. Next, we discuss the problem of permuting qubits among the nodes of the connectivity graph using only local operations, also known as routing. Using a fast quantum primitive to reverse the qubits in a chain, we construct a hybrid, quantum/classical routing algorithm on the chain. We show via rigorous bounds that this approach is faster than any SWAP-based algorithm for the same problem. The second part, which spans the final three chapters, discusses variational algorithms, which are a class of algorithms particularly suited to near-term quantum computation. Two prototypical variational algorithms, quantum adiabatic optimization (QAO) and the quantum approximate optimization algorithm (QAOA), are studied for the difference in their control strategies. We show that on certain crafted problem instances, bang-bang control (QAOA) can be as much as exponentially faster than quasistatic control (QAO). Next, we demonstrate the performance of variational state preparation on an analog quantum simulator based on trapped ions. We show that using classical heuristics that exploit structure in the variational parameter landscape, one can find circuit parameters efficiently in system size as well as circuit depth. In the experiment, we approximate the ground state of a critical Ising model with long-ranged interactions on up to 40 spins. Finally, we study the performance of Local Tensor, a classical heuristic algorithm inspired by QAOA on benchmarking instances of the MaxCut problem, and suggest physically motivated choices for the algorithm hyperparameters that are found to perform well empirically. We also show that our implementation of Local Tensor mimics imaginary-time quantum evolution under the problem Hamiltonian.

DOI
10.13016/1xzd-wupy

Related papers

Machine learning strategies for near-term quantum algorithms

Y.J. Patel

The central claim of this thesis is simple but underappreciated: the primary bottleneck in near-term quantum computing is not a shortage of algorithms; it is a lack of systematic decision-making. Which problem instances should we test? Which circuit architectures are worth training? Which hyperparameters actually drive performance, and which are distractions? Today’s quantum hardware sits in an uncomfortable middle ground. It is expressive enough to explore nontrivial quantum dynamics, yet it is too noisy and shallow for the theoretical speedups that motivate the field. This thesis argues that applying machine learning to classical control decisions in hybrid quantum classical methods is one of the most tractable ways to make these methods genuinely useful in this regime. This argument is developed through four research questions, each addressing a distinct decision-making layer and illustrating the thesis. The first asks whether the decisions inside a hybrid heuristic can be learned rather than hand-coded. Chapter 4 analyzes Recursive QAOA (RQAOA), a promising yet brittle approach to combinatorial optimization, and identifies regimes in which its fixed-elimination strategy fails. It then replaces that strategy with a reinforcement learning policy, RL-RQAOA, that adapts to instance structure. The resulting method performs better on the constructed failure cases while remaining competitive elsewhere. The broader point is that learned classical control policies can materially improve hybrid quantum heuristics without increasing quantum depth, which is a significant practical advantage on constrained hardware. The second question evaluates whether the quantum optimization algorithm benchmarking instances we use are principled. Chapter 5 observes that much benchmarking in this space is driven by convenience. Researchers test on whatever graphs are readily available and then report aggregate performance. Instead, the chapter proposes a generative pipeline that couples a permutation-invariant graph autoencoder with evolutionary optimization to deliberately construct Max-Cut instances that strongly discriminate between a quantum-inspired solver, RQAOA, and a strong classical baseline, Goemans-Williamson, in both directions. By connecting solver behavior to structural graph features, the chapter turns benchmarking from a static choice into an interpretable experimental tool. The generated instances also expose failure modes that random graphs often fail to reveal. The third question asks what changes when realistic noise constraints are taken seriously during circuit design, not only during execution. Chapter 6 develops RLQAS, a reinforcement learning framework for quantum architecture search that incorporates noise assumptions informed by real IBM device characteristics throughout training, rather than treating noise as a post hoc correction. Paired with an efficient Pauli transfer matrix simulation, the framework makes large-scale noisy circuit search computationally feasible. The circuits it discovers are compact, trainable, and achieve competitive accuracy on ground-state energy tasks. This suggests that hardware-aware circuit design is tractable and can yield materially different choices than noise-agnostic search. The fourth question asks: even when the circuit architecture is fixed, how much of what we attribute to quantum model design is actually due to hyperparameter sensitivity? Chapter 7 extends functional ANOVA to quantum neural networks to quantify which hyperparameter choices drive performance variance. The finding is clear. Learning rate, circuit depth, and data encoding/reuploading dominate, while many architectural micro-choices contribute far less than the literature often implies. Rather than stopping at diagnosis, the chapter turns these importance rankings into data-driven priors that accelerate hyperparameter optimization. It converts a critique into a practical improvement. Taken together, these contributions form a coherent toolkit for developing and evaluating hybrid quantum–classical methods in the NISQ regime. While the work does not eliminate the fundamental constraints of shallow, noisy hardware, it clarifies what can be improved immediately and how to do so in a reproducible manner. The broader goal is to help shift near-term quantum research from isolated demonstrations toward an engineering discipline, in which algorithms, benchmarks, and model-selection practices can be compared fairly, stress-tested rigorously, and iterated systematically as hardware matures.

•Nov 10, 2026•0 citations

Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices

Leo Zhou, Sheng-Tao Wang, Soonwon Choi +2 more

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.

arXiv:1812.01041•Physical Review X•Jun 24, 2020•1,132 citations

Quantum Approximate Optimization Algorithm and Variational Quantum Computing: from binary neural networks to ground state preparation

Pietro Torta

In this thesis, I explore the domain of hybrid quantum-classical computation, the foremost approach for utilizing Noisy Intermediate-Scale Quantum (NISQ) devices. The opening chapter presents an overview of Variational Quantum Algorithms (VQAs), highlighting the primary algorithmic challenges. It offers an in-depth review of the Quantum Approximate Optimization Algorithm (QAOA), discussing its variants for ground state preparation. In the second chapter, we apply QAOA for the supervised learning of a simple Binary Neural Network. This model represents an idealized yet prototypical example of classical combinatorial optimization problems involving multi-spin interactions. In the following chapters, the discussion shifts toward quantum many-body ground state preparation, focusing on the one-dimensional Heisenberg XYZ model and the longitudinal-transverse-field Ising model (LTFIM). We have developed a novel technique that, at any point in the phase diagram, leverages the transferability of a specific class of optimal schedules from systems with small to those with larger numbers of qubits. This approach mitigates trainability issues, specifically vanishing gradients (Barren Plateaus). Next, we tailor a QAOA scheme to characterize a topological quantum phase transition within a lattice gauge theory model. This investigation is particularly significant due to its implications for high-energy physics and relevance to quantum error correction and surface codes. In the concluding chapter, I propose new stimulating research directions and help to identify core challenges and unresolved questions in variational quantum computing that transcend any particular application domain.

•Apr 9, 2024•0 citations

Quantum Computing: Current Advances And Near-Term Applications

Win Mathew John

Quantum computing has transitioned from a theoretical curiosity to an emerging technological paradigm with demonstrable computational advantages in specific problem domains. This paper presents a comprehensive review of current advances in quantum computing hardware, software, and near-term applications within the Noisy Intermediate-Scale Quantum (NISQ) era. We examine the architectural evolution of leading quantum platforms, including superconducting, trapped-ion, and photonic systems, analyzing their qubit counts, gate fidelities, and coherence times. The paper evaluates key quantum algorithms Shor's factoring algorithm [1], Grover's search algorithm [2], the Variational Quantum Eigensolver (VQE) [3], and the Quantum Approximate Optimization Algorithm (QAOA) [4] in the context of their practical applicability to real-world problems. We further discuss the milestone of quantum computational advantage demonstrated by Google's Sycamore processor [5] and IBM's ambitious hardware roadmap toward fault-tolerant quantum computing [6]. Our analysis reveals that while universal fault-tolerant quantum computing remains a long-term objective, NISQ-era devices are already yielding valuable results in quantum chemistry simulation, combinatorial optimization, and quantum machine learning. We conclude by identifying the critical challenges—error correction, scalability, and algorithm design that must be addressed to realize the full potential of quantum computing.

•Apr 29, 2026•0 citations

Algorithm development for near-term quantum computers

Sim, Sukin

Fault-tolerant quantum computers, when realized, guarantee significant speedups for particular computational tasks. Quantum hardware in the near term, however, is limited to low hundreds of noisy qubits that are not error-corrected. To leverage such devices as well as accommodate rapid developments in both hardware and algorithms, variational quantum algorithms (VQAs) were introduced. These algorithms have the potential to be useful in areas such as chemistry, optimization, machine learning, among others. Despite this potential, the largest experiment to date has employed just twelve qubits to implement the Variational Quantum Eigensolver (VQE), a VQA for simulating ground state energies of fermionic systems. In this dissertation, we present several methods for extending and further developing VQAs to step closer towards realizing applications in which quantum computers can provide meaningful advantages over classical computers. In the first part, we present methods for analyzing and optimizing parameterized quantum circuits (PQCs), a core component in VQAs for approximating target quantum states, e.g. ground state wavefunctions in VQE. To compare among PQCs and guide their design and selection, we introduce a set of algorithm-independent descriptors that can be estimated from simulations. Using these descriptors, we rule out circuits with limited capabilities in expressive and entangling powers. Next, we present a strategy for optimizing PQCs with large parameter counts and high redundancy by removing circuit operations that are less important for optimizing the algorithm objective, effectively reducing the search space. We demonstrate that this method enables larger VQE simulations by converging previously difficult optimizations while additionally reducing circuit resources. In the second part, we present methods for developing VQAs that are related to the quantum hardware. We introduce a new algorithm for simulating components of a quantum processor using an existing quantum computer. The goal of this application is to leverage near-term devices and algorithms to aid in the design of more powerful next-generation quantum hardware. Lastly, we present a guide for algorithm prototyping by deploying instances of VQAs on quantum computers via the cloud. We demonstrate instances of two algorithms, the quantum autoencoder and classifier, on an eight-qubit device. While further advancements in hardware and algorithms lie ahead, our work, along with developments from previous studies, represents significant progress towards realizing practical quantum advantage.

•Jan 1, 2021•0 citations

An exponentially more efficient optimization algorithm for noisy quantum computers

Marko J. Rančić

Quantum computers are devices which allow the solution of problems unsolvable to their classical counterparts. As an error-corrected quantum computer is still a decade away the quantum computing community has dedicated much attention to developing algorithms for currently available Noisy Intermediate-Scale Quantum computers (NISQ). Thus far, within NISQ, optimization problems are one of the most commonly studied and are exclusively tackled with the Quantum Approximate Optimization Algorithm (QAOA). This algorithm predominantly computes graph partitions with a maximal separation of edges (MaxCut), but can also be modified to calculate other properties of graphs. Here, I present a novel quantum optimization algorithm which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem. Such an improved performance allowed me to partition a graphs 32 nodes on publicly available 5 qubit gate-based solid state quantum devices without any preprocessing such as division of the graph into smaller subgraphs. This results represent a 40% increase in graph size as compared to state-of-art experiments on solid state devices such as Google Sycamore. The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal quantum simulators. Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with quantum simulators, again without any pre-division into smaller subproblems and a lower solution bound of 67.9% is achieved.

•Oct 22, 2021•3 citations
Quantum computers have come a long way since conception, and there is still a long way to go before the dream of universal, fault-tolerant computation is realized. In the near term, quantum computers will occupy a middle ground that is popularly known as the “Noisy, Intermediate-Scale Quantum” (or NISQ) regime. The NISQ era represents a transition in the nature of quantum devices from experimental to computational. There is significant interest in engineering NISQ devices and NISQ algorithms in a manner that will guide the development of quantum computation in this regime and into the era of fault-tolerant quantum computing. In this thesis, we study two aspects of near-term quantum computation. The first of these is the design of device architectures, covered in Chapters 2, 3, and 4. We examine different qubit connectivities on the basis of their graph properties, and present numerical and analytical results on the speed at which large entangled states can be created on nearest-neighbor grids and graphs with modular structure. Next, we discuss the problem of permuting qubits among the nodes of the connectivity graph using only local operations, also known as routing. Using a fast quantum primitive to reverse the qubits in a chain, we construct a hybrid, quantum/classical routing algorithm on the chain. We show via rigorous bounds that this approach is faster than any SWAP-based algorithm for the same problem. The second part, which spans the final three chapters, discusses variational algorithms, which are a class of algorithms particularly suited to near-term quantum computation. Two prototypical variational algorithms, quantum adiabatic optimization (QAO) and the quantum approximate optimization algorithm (QAOA), are studied for the difference in their control strategies. We show that on certain crafted problem instances, bang-bang control (QAOA) can be as much as exponentially faster than quasistatic control (QAO). Next, we demonstrate the performance of variational state preparation on an analog quantum simulator based on trapped ions. We show that using classical heuristics that exploit structure in the variational parameter landscape, one can find circuit parameters efficiently in system size as well as circuit depth. In the experiment, we approximate the ground state of a critical Ising model with long-ranged interactions on up to 40 spins. Finally, we study the performance of Local Tensor, a classical heuristic algorithm inspired by QAOA on benchmarking instances of the MaxCut problem, and suggest physically motivated choices for the algorithm hyperparameters that are found to perform well empirically. We also show that our implementation of Local Tensor mimics imaginary-time quantum evolution under the problem Hamiltonian.
The central claim of this thesis is simple but underappreciated: the primary bottleneck in near-term quantum computing is not a shortage of algorithms; it is a lack of systematic decision-making. Which problem instances should we test? Which circuit architectures are worth training? Which hyperparameters actually drive performance, and which are distractions? Today’s quantum hardware sits in an uncomfortable middle ground. It is expressive enough to explore nontrivial quantum dynamics, yet it is too noisy and shallow for the theoretical speedups that motivate the field. This thesis argues that applying machine learning to classical control decisions in hybrid quantum classical methods is one of the most tractable ways to make these methods genuinely useful in this regime. This argument is developed through four research questions, each addressing a distinct decision-making layer and illustrating the thesis. The first asks whether the decisions inside a hybrid heuristic can be learned rather than hand-coded. Chapter 4 analyzes Recursive QAOA (RQAOA), a promising yet brittle approach to combinatorial optimization, and identifies regimes in which its fixed-elimination strategy fails. It then replaces that strategy with a reinforcement learning policy, RL-RQAOA, that adapts to instance structure. The resulting method performs better on the constructed failure cases while remaining competitive elsewhere. The broader point is that learned classical control policies can materially improve hybrid quantum heuristics without increasing quantum depth, which is a significant practical advantage on constrained hardware. The second question evaluates whether the quantum optimization algorithm benchmarking instances we use are principled. Chapter 5 observes that much benchmarking in this space is driven by convenience. Researchers test on whatever graphs are readily available and then report aggregate performance. Instead, the chapter proposes a generative pipeline that couples a permutation-invariant graph autoencoder with evolutionary optimization to deliberately construct Max-Cut instances that strongly discriminate between a quantum-inspired solver, RQAOA, and a strong classical baseline, Goemans-Williamson, in both directions. By connecting solver behavior to structural graph features, the chapter turns benchmarking from a static choice into an interpretable experimental tool. The generated instances also expose failure modes that random graphs often fail to reveal. The third question asks what changes when realistic noise constraints are taken seriously during circuit design, not only during execution. Chapter 6 develops RLQAS, a reinforcement learning framework for quantum architecture search that incorporates noise assumptions informed by real IBM device characteristics throughout training, rather than treating noise as a post hoc correction. Paired with an efficient Pauli transfer matrix simulation, the framework makes large-scale noisy circuit search computationally feasible. The circuits it discovers are compact, trainable, and achieve competitive accuracy on ground-state energy tasks. This suggests that hardware-aware circuit design is tractable and can yield materially different choices than noise-agnostic search. The fourth question asks: even when the circuit architecture is fixed, how much of what we attribute to quantum model design is actually due to hyperparameter sensitivity? Chapter 7 extends functional ANOVA to quantum neural networks to quantify which hyperparameter choices drive performance variance. The finding is clear. Learning rate, circuit depth, and data encoding/reuploading dominate, while many architectural micro-choices contribute far less than the literature often implies. Rather than stopping at diagnosis, the chapter turns these importance rankings into data-driven priors that accelerate hyperparameter optimization. It converts a critique into a practical improvement. Taken together, these contributions form a coherent toolkit for developing and evaluating hybrid quantum–classical methods in the NISQ regime. While the work does not eliminate the fundamental constraints of shallow, noisy hardware, it clarifies what can be improved immediately and how to do so in a reproducible manner. The broader goal is to help shift near-term quantum research from isolated demonstrations toward an engineering discipline, in which algorithms, benchmarks, and model-selection practices can be compared fairly, stress-tested rigorously, and iterated systematically as hardware matures.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems.Despite its promise for near-term quantum applications, not much is currently understood about the QAOA's performance beyond its lowestdepth variant.An essential but missing ingredient for understanding and deploying the QAOA is a constructive approach to carry out the outer-loop classical optimization.We provide an in-depth study of the performance of the QAOA on MaxCut problems by developing an efficient parameter-optimization procedure and revealing its ability to exploit nonadiabatic operations.Building on observed patterns in optimal parameters, we propose heuristic strategies for initializing optimizations to find quasioptimal p-level QAOA parameters in O½polyðpÞ time, whereas the standard strategy of random initialization requires 2 OðpÞ optimization runs to achieve similar performance.We then benchmark the QAOA and compare it with quantum annealing, especially on difficult instances where adiabatic quantum annealing fails due to small spectral gaps.The comparison reveals that the QAOA can learn via optimization to utilize nonadiabatic mechanisms to circumvent the challenges associated with vanishing spectral gaps.Finally, we provide a realistic resource analysis on the experimental implementation of the QAOA.When quantum fluctuations in measurements are accounted for, we illustrate that optimization is important only for problem sizes beyond numerical simulations but accessible on near-term devices.We propose a feasible implementation of large MaxCut problems with a few hundred vertices in a system of 2D neutral atoms, reaching the regime to challenge the best classical algorithms.
In this thesis, I explore the domain of hybrid quantum-classical computation, the foremost approach for utilizing Noisy Intermediate-Scale Quantum (NISQ) devices. The opening chapter presents an overview of Variational Quantum Algorithms (VQAs), highlighting the primary algorithmic challenges. It offers an in-depth review of the Quantum Approximate Optimization Algorithm (QAOA), discussing its variants for ground state preparation. In the second chapter, we apply QAOA for the supervised learning of a simple Binary Neural Network. This model represents an idealized yet prototypical example of classical combinatorial optimization problems involving multi-spin interactions. In the following chapters, the discussion shifts toward quantum many-body ground state preparation, focusing on the one-dimensional Heisenberg XYZ model and the longitudinal-transverse-field Ising model (LTFIM). We have developed a novel technique that, at any point in the phase diagram, leverages the transferability of a specific class of optimal schedules from systems with small to those with larger numbers of qubits. This approach mitigates trainability issues, specifically vanishing gradients (Barren Plateaus). Next, we tailor a QAOA scheme to characterize a topological quantum phase transition within a lattice gauge theory model. This investigation is particularly significant due to its implications for high-energy physics and relevance to quantum error correction and surface codes. In the concluding chapter, I propose new stimulating research directions and help to identify core challenges and unresolved questions in variational quantum computing that transcend any particular application domain.
Quantum computing has transitioned from a theoretical curiosity to an emerging technological paradigm with demonstrable computational advantages in specific problem domains. This paper presents a comprehensive review of current advances in quantum computing hardware, software, and near-term applications within the Noisy Intermediate-Scale Quantum (NISQ) era. We examine the architectural evolution of leading quantum platforms, including superconducting, trapped-ion, and photonic systems, analyzing their qubit counts, gate fidelities, and coherence times. The paper evaluates key quantum algorithms Shor's factoring algorithm [1], Grover's search algorithm [2], the Variational Quantum Eigensolver (VQE) [3], and the Quantum Approximate Optimization Algorithm (QAOA) [4] in the context of their practical applicability to real-world problems. We further discuss the milestone of quantum computational advantage demonstrated by Google's Sycamore processor [5] and IBM's ambitious hardware roadmap toward fault-tolerant quantum computing [6]. Our analysis reveals that while universal fault-tolerant quantum computing remains a long-term objective, NISQ-era devices are already yielding valuable results in quantum chemistry simulation, combinatorial optimization, and quantum machine learning. We conclude by identifying the critical challenges—error correction, scalability, and algorithm design that must be addressed to realize the full potential of quantum computing.
Fault-tolerant quantum computers, when realized, guarantee significant speedups for particular computational tasks. Quantum hardware in the near term, however, is limited to low hundreds of noisy qubits that are not error-corrected. To leverage such devices as well as accommodate rapid developments in both hardware and algorithms, variational quantum algorithms (VQAs) were introduced. These algorithms have the potential to be useful in areas such as chemistry, optimization, machine learning, among others. Despite this potential, the largest experiment to date has employed just twelve qubits to implement the Variational Quantum Eigensolver (VQE), a VQA for simulating ground state energies of fermionic systems. In this dissertation, we present several methods for extending and further developing VQAs to step closer towards realizing applications in which quantum computers can provide meaningful advantages over classical computers. In the first part, we present methods for analyzing and optimizing parameterized quantum circuits (PQCs), a core component in VQAs for approximating target quantum states, e.g. ground state wavefunctions in VQE. To compare among PQCs and guide their design and selection, we introduce a set of algorithm-independent descriptors that can be estimated from simulations. Using these descriptors, we rule out circuits with limited capabilities in expressive and entangling powers. Next, we present a strategy for optimizing PQCs with large parameter counts and high redundancy by removing circuit operations that are less important for optimizing the algorithm objective, effectively reducing the search space. We demonstrate that this method enables larger VQE simulations by converging previously difficult optimizations while additionally reducing circuit resources. In the second part, we present methods for developing VQAs that are related to the quantum hardware. We introduce a new algorithm for simulating components of a quantum processor using an existing quantum computer. The goal of this application is to leverage near-term devices and algorithms to aid in the design of more powerful next-generation quantum hardware. Lastly, we present a guide for algorithm prototyping by deploying instances of VQAs on quantum computers via the cloud. We demonstrate instances of two algorithms, the quantum autoencoder and classifier, on an eight-qubit device. While further advancements in hardware and algorithms lie ahead, our work, along with developments from previous studies, represents significant progress towards realizing practical quantum advantage.
Quantum computers are devices which allow the solution of problems unsolvable to their classical counterparts. As an error-corrected quantum computer is still a decade away the quantum computing community has dedicated much attention to developing algorithms for currently available Noisy Intermediate-Scale Quantum computers (NISQ). Thus far, within NISQ, optimization problems are one of the most commonly studied and are exclusively tackled with the Quantum Approximate Optimization Algorithm (QAOA). This algorithm predominantly computes graph partitions with a maximal separation of edges (MaxCut), but can also be modified to calculate other properties of graphs. Here, I present a novel quantum optimization algorithm which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem. Such an improved performance allowed me to partition a graphs 32 nodes on publicly available 5 qubit gate-based solid state quantum devices without any preprocessing such as division of the graph into smaller subgraphs. This results represent a 40% increase in graph size as compared to state-of-art experiments on solid state devices such as Google Sycamore. The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal quantum simulators. Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with quantum simulators, again without any pre-division into smaller subproblems and a lower solution bound of 67.9% is achieved.