One of the main challenges faced by researchers in the field of quantum computing is the problemof noise in quantum systems. Noise can significantly limit the performance of quantum algorithms.It is in this context that our research, aimed at the development and optimization of quantumalgorithms with a focus on depth, is updated. The depth of quantum circuits is one of the critical parametersin the development of quantum algorithms. Optimized circuits with improved depth have the potential to significantly reduce the impact of noise, which in turn should lead to improved efficiency.We aim to provide solutions that not only address technical constraints, but also provide practicalresults for quantum computing in the context of optimization problems. This study analyzes the use ofa quantum approximate optimization algorithm for solving complex combinatorial optimizationproblems. However, in the process of using this algorithm we encounter a serious limitation – noisein the quantum system, which significantly reduces its efficiency. To overcome the influence of noiseand improve the efficiency of quantum algorithms, several methods have been proposed. This paperpresents a greedy heuristic algorithm aimed at reducing the impact of noise. The main goal of thisalgorithm is to find a spanning tree of minimum height. This, in turn, reduces the overall depth ofquantum circuits and minimizes the number of CNOT gates, which is key to optimizing quantumcomputing. Through numerical analysis, it was demonstrated that the proposed greedy heuristicalgorithm is capable of significantly increasing the probability of successful completion of each iterationin the problem of finding the maximum cut in a graph by 10 times. Moreover, the study confirmsthat the average depth of the quantum circuit generated by the proposed heuristic algorithm is stilllinearly dependent on the size of the input data, but the slope of this linear dependence is reducedfrom 1 to 0.11 by using the proposed method.
One of the main challenges faced by researchers in the field of quantum computing is the problemof noise in quantum systems. Noise can significantly limit the performance of quantum algorithms.It is in this context that our research, aimed at the development and optimization of quantumalgorithms with a focus on depth, is updated. The depth of quantum circuits is one of the critical parametersin the development of quantum algorithms. Optimized circuits with improved depth have the potential to significantly reduce the impact of noise, which in turn should lead to improved efficiency.We aim to provide solutions that not only address technical constraints, but also provide practicalresults for quantum computing in the context of optimization problems. This study analyzes the use ofa quantum approximate optimization algorithm for solving complex combinatorial optimizationproblems. However, in the process of using this algorithm we encounter a serious limitation – noisein the quantum system, which significantly reduces its efficiency. To overcome the influence of noiseand improve the efficiency of quantum algorithms, several methods have been proposed. This paperpresents a greedy heuristic algorithm aimed at reducing the impact of noise. The main goal of thisalgorithm is to find a spanning tree of minimum height. This, in turn, reduces the overall depth ofquantum circuits and minimizes the number of CNOT gates, which is key to optimizing quantumcomputing. Through numerical analysis, it was demonstrated that the proposed greedy heuristicalgorithm is capable of significantly increasing the probability of successful completion of each iterationin the problem of finding the maximum cut in a graph by 10 times. Moreover, the study confirmsthat the average depth of the quantum circuit generated by the proposed heuristic algorithm is stilllinearly dependent on the size of the input data, but the slope of this linear dependence is reducedfrom 1 to 0.11 by using the proposed method.
While a Quantum Approximate Optimization Algorithm (QAOA) is intended to provide a quantum advantage in finding approximate solutions to combinatorial optimization problems, noise in the system is a hurdle in exploiting its full potential. Several error mitigation techniques have been studied to lessen the effect of noise on this algorithm. Recently, Majumdar et al. proposed a Depth First Search (DFS) based method to reduce n−1 CNOT gates in the ansatz design of QAOA for finding Max-Cut in a graph G = (V, E), |V| = n. However, this method tends to increase the depth of the circuit, making it more prone to relaxation error. The depth of the circuit is proportional to the height of the DFS tree, which can be n−1 in the worst case. In this paper, we propose an O(Δ⋅n2) greedy heuristic algorithm, where Δ is the maximum degree of the graph, that finds a spanning tree of lower height, thus reducing the overall depth of the circuit while still retaining the n−1 reduction in the number of CNOT gates needed in the ansatz. We numerically show that this algorithm achieves nearly 10 times increase in the probability of success for each iteration of QAOA for Max-Cut. We further show that although the average depth of the circuit produced by this heuristic algorithm still grows linearly with n, our algorithm reduces the slope of the linear increase from 1 to 0.11.
We introduce a quantum algorithm that produces approximate solutions for combinatorial optimization problems. The algorithm depends on a positive integer p and the quality of the approximation improves as p is increased. The quantum circuit that implements the algorithm consists of unitary gates whose locality is at most the locality of the objective function whose optimum is sought. The depth of the circuit grows linearly with p times (at worst) the number of constraints. If p is fixed, that is, independent of the input size, the algorithm makes use of efficient classical preprocessing. If p grows with the input size a different strategy is proposed. We study the algorithm as applied to MaxCut on regular graphs and analyze its performance on 2-regular and 3-regular graphs for fixed p. For p = 1, on 3-regular graphs the quantum algorithm always finds a cut that is at least 0.6924 times the size of the optimal cut.
This work reviews methods for optimizing quantum circuit depth, encompassing theoretical techniques, algorithmic innovations, and practical applications. Recent advancements demonstrate substantial improvements in circuit depth optimization, yet the issue of scalability remains unresolved. Key research contributions, such as the advanced exact synthesis of Clifford+T circuits, have shown promising results in reducing the number of T-gates, thus enhancing computational efficiency. However, the practical implementation of these methods in real-world noisy environments has yet to be fully evaluated. Further studies have developed automated optimization techniques for large quantum circuits with continuous parameters, significantly minimizing gate counts while maintaining structural integrity. Despite these advancements, challenges persist in assessing the performance of these optimized circuits on actual quantum hardware and integrating them into various quantum algorithms. The qubit routing problem also presents significant hurdles, particularly in systems with limited communication, necessitating effective methodologies to optimize qubit placement and movement. A comprehensive full-stack approach, incorporating hardware, software, and compiler optimizations, has provided valuable insights into architectural comparisons and design strategies. This approach highlights the importance of noise-aware compilation and the need for microarchitecture-specific optimizations to improve program success rates on current quantum devices. This paper underscores the need for scalable, hardware-agnostic optimization methods and extensive experimental validation. Integrating graph neural networks for quantum circuit optimization presents a promising future research direction. The analysis concludes that while significant progress has been made, unresolved issues such as computational complexity, limited experimental validation, and the diversity of quantum algorithms necessitate ongoing research to fully realize the potential of quantum computing. In conclusion, optimizing the depth of quantum circuits is a multifaceted problem requiring continuous research and development. The integration of theoretical advancements with practical implementations is crucial for overcoming current limitations and unlocking the full potential of quantum computing. Continued efforts in this area will be vital for achieving scalable and efficient quantum computations
Quantum Approximate Optimization Algorithm (QAOA) is a prospective candidate for providing quantum advantage in finding approximate solutions to optimization problems using near-term quantum devices. In this paper, the goal is to reduce the number of CNOT gates and the depth of quantum ansatz circuits for QAOA. First, we present a generalized QAOA formulation for any Hamiltonian that involves upto two-body interactions, as a graph. The circuit realization of the depth-p QAOA requires 2mp CNOT gates where the graph for the Hamiltonian has n vertices and m edges. Presently, a CNOT gate is one of the primary sources of error. We propose a graph-theoretic algorithm which can eliminate n−1 CNOTs from the QAOA ansatz while retaining functional equivalence with the original circuit. This improves upon previously proposed Depth First Search (DFS) method by restricting the increase in depth of the circuit, which was a drawback of the method, by ≃84.8% for Erdős-Renyi graphs. Finally, if the underlying connectivity (hardware coupling map) and the initial qubit placement for a hardware are known, then we present how to extend the greedy heuristic method in order to obtain a functionally equivalent circuit with ≃5%; fewer SWAP gates for Erdős-Renyi graphs.
The current noisy intermediate-scale quantum (NISQ) era is characterized by substantial errors and noise, which limit the practical feasibility of deep, many-qubit circuits. To address these constraints, quantum circuit cutting has emerged as a promising tool. Recently, there has been significant research on methods for performing such cutting effectively. In this work, the duality between quantum circuits and classical graphs - specifically, directed acyclic graphs (dags) - is leveraged to analyze the complexity of finding an optimal circuit-cutting configuration that minimizes the number of cuts. After developing a rigorous graph-theoretic framework, the complexity of identifying cut locations that partition a given quantum circuit into smaller fragments is characterized. The corresponding graph-combinatorial task is then defined, and the resulting partition problem is shown to be NP-complete. Furthermore, even a simplified version of the problem, restricted to circuits composed only of one- and two-qubit gates, is shown to be NP-complete. Finally, based on these constraints, an algorithm grounded in satisfiability modulo theories (SMT) is proposed to find optimal cuts when the number of qubits per partition is bounded. This work therefore provides a complexity-theoretic characterization of cut placement and a practical solver for bounded-size decompositions.
The max-cut problem (MCP) is a classic problem in the field of combinatorial optimization and has important applications in various fields, including statistical physics and image processing. However, except for some special cases, the MCP still encounters a non-deterministic polynomial complete problem (an NP-complete problem), and there is currently no known efficient classical algorithm that can solve it in polynomial time. The quantum approximate optimization algorithm (QAOA), as a pivotal algorithm in the noisy intermediate-scale quantum (NISQ) computing era, has shown significant potential for solving the MCP. However, due to the lack of quantum error correction, the reliability of computations in NISQ systems sharply declines as the circuit depth of the algorithm increases. Therefore, designing an efficient, shallow-depth, and low-complexity QAOA for the MCP is a critical challenge in demonstrating the advantages of quantum computing in the NISQ era.In this paper, according to the standard QAOA algorithm, we introduce Pauli Y rotation gates into the target Hamiltonian circuit for the MCP. By enhancing the flexibility of quantum trial functions and improving the efficiency of Hilbert space exploration within a single iteration, we significantly improve the performance of QAOA on the MCP.We conduct extensive numerical simulations using the MindSpore quantum platform, and compare the proposed RY-layer-assisted QAOA with standard QAOA and its existing variants, including MA-QAOA and QAOA+. The experiments are performed on various graph types, including complete graphs, 3-regular graphs, 4-regular graphs, and random graphs with edge probabilities between 0.3 and 0.5. Our results show that the RY-layer-assisted QAOA achieves higher approximation ratios in all graph types, particularly in regular and random graphs, where traditional QAOA variants are difficult to implement. Moreover, the proposed method exhibits strong robustness as the graph size increases, and can maintain high performance even for larger graphs. Importantly, the RY-layer-assisted QAOA requires fewer CNOT gates and has a lower circuit depth than the standard QAOA and its variants, making it more suitable for NISQ devices with limited coherence times and high error rates.In conclusion, the RY-layer-assisted QAOA provides a promising approach for solving MCP in the NISQ era. By improving the approximation ratio while reducing circuit complexity, this method demonstrates significant potential for practical quantum computing applications, thus paving the way for developing more efficient and reliable quantum optimization algorithms.