With the rapid development of quantum computers in recent years, the importance of performance evaluation in quantum algorithms has been increasing. One method that has gained attention for performing this evaluation on classical computers is tensor networks. Tensor networks not only reduce the computational cost required for simulations by using approximations but are also deeply connected to entanglement. Entanglement is one of the most important elements for the quantum advantages of quantum algorithms, but the direct relationship between quantum advantages and entanglement remains largely unexplored. Tensor networks are promising as a means to address this question. In this study, we focus on the entanglement in the Quantum Approximate Optimization Algorithm (QAOA). This study aims to investigate entanglement in QAOA by examining the relationship between the approximation rates of tensor networks and the performance of QAOA. Specifically, we actually perform tensor network simulations of QAOA on a classical computer and extend the study of the scaling relations presented in previous research. We have discovered that scaling relations hold even when entanglement entropy is used as the vertical axis. Furthermore, by analyzing the results of the numerical calculations, we propose a new function for the scaling relation. Additionally, we discovered interesting relationships regarding the behavior of entanglement in QAOA during our analysis. This research is expected to provide new insights into the theoretical foundation of the scaling relations presented in previous studies.
With the rapid development of quantum computers in recent years, the importance of performance evaluation in quantum algorithms has been increasing. One method that has gained attention for performing this evaluation on classical computers is tensor networks. Tensor networks not only reduce the computational cost required for simulations by using approximations but are also deeply connected to entanglement. Entanglement is one of the most important elements for the quantum advantages of quantum algorithms, but the direct relationship between quantum advantages and entanglement remains largely unexplored. Tensor networks are promising as a means to address this question. In this study, we focus on the entanglement in the Quantum Approximate Optimization Algorithm (QAOA). This study aims to investigate entanglement in QAOA by examining the relationship between the approximation rates of tensor networks and the performance of QAOA. Specifically, we actually perform tensor network simulations of QAOA on a classical computer and extend the study of the scaling relations presented in previous research. We have discovered that scaling relations hold even when entanglement entropy is used as the vertical axis. Furthermore, by analyzing the results of the numerical calculations, we propose a new function for the scaling relation. Additionally, we discovered interesting relationships regarding the behavior of entanglement in QAOA during our analysis. This research is expected to provide new insights into the theoretical foundation of the scaling relations presented in previous studies.
Entanglement is widely regarded as a key resource underlying the power of quantum algorithms and their potential to achieve quantum advantage. With the emergence of variational quantum algorithms, however, questions have arisen regarding how entanglement relates to problem structure and algorithmic performance in near-term quantum applications. Here, we examine this relationship through the Quantum Approximate Optimization Algorithm (QAOA), a specific class of variational algorithms, applied to the MaxCut problem. We show that suboptimal variational parameter training can significantly modify the observed entanglement profile, obscuring its scaling behavior. By employing a high-performance optimizer, we find empirical evidence that QAOA exhibits entanglement scaling consistent with that of fermionic Gaussian states (up to a scaling factor) across a broad range of MaxCut instances. We further compare these results with adiabatic quantum computation, observing annealing-schedule-dependent entanglement profiles whose scaling behavior differs markedly from that of QAOA. Together, these findings provide new insight into how entanglement manifests in and distinguishes these two algorithmic paradigms, highlighting its connection to both computational performance and problem structure.
Many quantum algorithms seek to output a specific bitstring solving the problem of interest---or a few if the solution is degenerate. It is the case for the quantum approximate optimization algorithm (QAOA) in the limit of large circuit depth, which aims to solve quadratic unconstrained binary optimization problems. Hence, the expected final state for these algorithms is either a product state or a low-entangled superposition involving a few bitstrings. What happens in between the initial N-qubit product state ${|0\ensuremath{\rangle}}^{\ensuremath{\bigotimes}N}$ and the final one regarding entanglement? Here, we consider the QAOA algorithm for solving the paradigmatic MaxCut problem on different types of graphs. We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits and find that there is a volume-law entanglement barrier between the initial and final states. We also investigate the entanglement spectrum in connection with random matrix theory. In addition, we compare the entanglement production with a quantum annealing protocol aiming to solve the same MaxCut problems. Finally, we discuss the implications of our results for the simulation of QAOA circuits with tensor network-based methods relying on low-entanglement for efficiency, such as matrix product states.
Quantum computing has emerged as a promising paradigm to tackle computationally intensive problems that classical computers struggle with. In this study, we explore the application of the Edge-based quantum approximate optimization algorithm (QAOA) to the MAX-CUT problem, a well-known combinatorial optimization challenge. MAX-CUT aims to partition the vertices of a graph into two subsets such that the number of edges between the subsets is maximized. We define the edge-based MAX-CUT problem and propose a method for applying QAOA specifically tailored to this formulation. We conduct simulations using IBM’s Qiskit framework, examining both vertex-based and edge-based QAOA implementations across various graph structures. Our results highlight the comparative performance of these approaches in terms of solution quality and computational efficiency. Specifically, we analyze the impact of different graph sizes and edge densities on the complexity and CNOT gate counts of the proposed algorithms. This analysis provides insights into leveraging quantum computing for combinatorial optimization tasks, particularly focusing on the implications for practical applications and future research directions.
This research explores the integration of the Quantum Approximate Optimization Algorithm (QAOA) into Hybrid Quantum-HPC systems for solving the Max-Cut problem, comparing its performance with classical algorithms like brute-force search and greedy heuristics. We develop a theoretical model to analyze the time complexity, scalability, and communication overhead in hybrid systems. Using simulations, we evaluate QAOA's performance on small-scale Max-Cut instances, benchmarking its runtime, solution accuracy, and resource utilization. The study also investigates the scalability of QAOA with increasing problem size, offering insights into its potential advantages over classical methods for large-scale combinatorial optimization problems, with implications for future Quantum computing applications in HPC environments.
Quantum annealing and quantum approximate optimization algorithms hold a great potential to speed-up optimization problems. This could be game-changing for a plethora of applications. Yet, in order to hope to beat classical solvers, quantum circuits must scale up to sizes and performances much beyond current hardware. In that quest, intense experimental effort has been recently devoted to optimizations on 3-regular graphs, which are computationally hard but experimentally relatively amenable. However, even there, the amount and quality of quantum resources required for quantum solvers to outperform classical ones is unclear. Here, we show that quantum annealing for 3-regular graphs can be classically simulated even at scales of 1000 qubits and 5000000 two-qubit gates with all-to-all connectivity. To this end, we develop a graph tensor-network quantum annealer (GTQA) able of high-precision simulations of Trotterized circuits of near-adiabatic evolutions. Based on a recently proposed belief-propagation technique for tensor canonicalization, GTQA is equipped with re-gauging and truncation primitives that keep approximation errors small in spite of the circuits generating significant amounts of entanglement. As a result, even with a maximal bond dimension as low as 4, GTQA produces solutions competitive with those of state-of-the-art classical solvers. For non-degenerate instances, the unique solution can be read out from the final reduced single-qubit states. In contrast, for degenerate problems, such as MaxCut, we introduce an approximate measurement simulation algorithm for graph tensor-network states. On one hand, our findings showcase the potential of GTQA as a powerful quantum-inspired optimizer. On the other hand, they considerably raise the bar required for experimental demonstrations of quantum speed-ups in combinatorial optimizations.
Entanglement is a key property of quantum computing that separates it from its classical counterpart; however, its exact role in the performance of quantum algorithms, especially variational quantum algorithms, is not well understood. In this work, we utilize tensor network methods to systematically probe the role of entanglement in the working of two variational quantum algorithms, the quantum approximate optimization algorithm (QAOA) and quantum neural networks (QNNs), on prototypical problems under controlled entanglement environments. We find that for the max-cut problem solved using QAOA, the fidelity as a function of entanglement is highly dependent on the number of layers, layout of edges in the graph, and edge density, generally exhibiting that a high number of layers indicates a higher resilience to truncation of entanglement. This is in contrast to previous studies based on no more than four QAOA layers which show that the fidelity of QAOA follows a scaling law for circuits. Contrarily, in the case of QNNs, trained circuits with high test accuracies are underpinned by higher entanglement, with any enforced limitation in entanglement resulting in a sharp decline in test accuracy. This is corroborated by the entanglement entropy of these circuits which is consistently high suggesting that, unlike QAOA, QNNs may require quantum devices capable of generating highly entangled states. Overall, our work provides a deeper understanding of the role of entanglement in the working of variational quantum algorithms which may help to implement these algorithms on NISQ-era quantum hardware in a way that maximizes their accuracies.