A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.
A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.
A novel quantum algorithm named the Quantum Approximate Shift-Phase Algorithm (QASPA) is proposed for the approximate solution of the Max-Cut problem. The Max-Cut problem consists in partitioning the set of vertices into two subsets in such a way that the total weight of the edges connecting vertices from different subsets is maximized. This problem is known to be NP-complete and represents a combinatorial challenge. Classical solution algorithms require excessive computational time, rendering them inefficient for medium and large graphs. Approximate solution methods offer guaranteed approximation ratios but still face significant limitations in terms of accuracy and performance on larger graphs. The proposed algorithm features a simple scheme and a minimal number of optimized parameters. The input graph is represented by an adjacency matrix, after which the edge weights are linearly normalized to fixed phase angles. The quantum circuit begins by applying a Hadamard transform to each qubit, thereby creating an equal superposition of all possible partitions. Subsequently, for each pair of adjacent vertices, a sequence comprising a controlled NOT gate, a single-qubit rotation around the Y-axis by an angle proportional to the edge weight, and a second controlled NOT gate is applied. This encodes the phase information about the edge weights into the quantum state of the system. After circuit execution, the qubits are measured in the standard computational basis, and the resulting probability distribution allows the selection of the most probable partition as an approximate solution to the problem. Experimental studies conducted on quantum processor simulators have demonstrated that the proposed algorithm achieves accuracy comparable to the Variational Quantum Approximate Optimization Algorithm (QAOA) while significantly reducing computation time due to the absence of iterative parameter optimization. Moreover, as the graph size increases, the algorithm's runtime grows considerably slower compared to classical brute-force approaches and QAOA, confirming its potential for solving medium-sized Max-Cut problems.
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.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is one of the promising near-term algorithms designed to find approximate solutions for combinatorial optimization problems. The algorithm prepares a parametrized state that is aimed to maximize the expectation value of the objective function of the problem. The circuit for QAOA consists of p layers, and it depends on 2p parameters, the determination of which can be carried out using a variational quantum eigensolver (VQE) subroutine. This is a variational approach for finding optimal parameters, where the quantum state is prepared with a quantum computer, and a classical computer is used for calculating the corresponding objective function value and performing an outer loop optimization routine in order to find optimal parameters. Earlier work on the algorithm has shown that QAOA is closely related to the Quantum Adiabatic Algorithm, which results in noticeable patterns in the optimal parameters. To this purpose, two methods, INTERP and FOURIER, were proposed to exploit this structure by Zhou et al. (2018). In this thesis, I extend upon these results by examining the effectiveness of one of their methods, the INTERP method, on the Max-Cut problem from graph theory. The performance of QAOA using this method was studied on several classes of graphs and benchmarked against the currently best-known classical algorithm Goemans-Williamson, which achieves an approximation ratio of ρ ≈ 0.878 on arbitrary graphs. The classes of graphs examined include cyclic, weighted and unweighted 3-regular, and Erdős–Rényi graphs with edge probabilities of 0.5 and 0.75 and graph sizes ranging from 4 to 16. Moreover, it was investigated if the INTERP method offers an advantage compared to random initialization of parameters and whether or not the method is polynomial in p. It was found that different graph classes lead to similar but different parameter patterns. Furthermore, the performance of QAOA using the INTERP method was dependent on the graph class considered. For the small graphs investigated it was found that QAOA outperforms Goemans-Williamson on ER-0.50, ER-0.75 and weighted 3-regular graphs from p=7 and beyond with respect to how well the expectation of the objective function approximates the optimal value, while for unweighted 3-regular graphs p=6 suffices. However, the calculation of the parameters is costly and requires a number of function evaluations that is on the order of the number of possible bipartitions of small graph with sizes n ≤ 16. Moreover, the numerical results suggested that indeed the method is polynomial in p advocating that the algorithm might be a strong alternative to Goemans-Williamson for large graph sizes, once hardware allows it.
The weighted MAX k-CUT problem consists of finding a k-partition of a given weighted undirected graph G(V,E) such that the sum of the weights of the crossing edges is maximized. The problem is of particular interest as it has a multitude of practical applications. We present a formulation of the weighted MAX k-CUT suitable for running the quantum approximate optimization algorithm (QAOA) on noisy intermediate scale quantum (NISQ)-devices to get approximate solutions. The new formulation uses a binary encoding that requires only |V|log_2(k) qubits. The contributions of this paper are as follows: i) A novel decomposition of the phase separation operator based on the binary encoding into basis gates is provided for the MAX k-CUT problem for k >2. ii) Numerical simulations on a suite of test cases comparing different encodings are performed. iii) An analysis of the resources (number of qubits, CX gates) of the different encodings is presented. iv) Formulations and simulations are extended to the case of weighted graphs. For small k and with further improvements when k is not a power of two, our algorithm is a possible candidate to show quantum advantage on NISQ devices.
Optimizing parameterized quantum circuits promises efficient use of near-term quantum devices to achieve potential quantum advantage. However, there is a notorious tradeoff between the expressibility and trainability of the parameter ansatz. We find that in combinatorial optimization problems, since the solutions are described by bit strings, one can trade the expressiveness of the ansatz for high train ability. To be specific, by focusing on the max-cut problem we introduce a simple yet efficient algorithm named Quantum Qubit Rotation Algorithm (QQRA). The quantum circuits are comprised with single-qubit rotation gates implementing on each qubit. The rotation angles of the gates can be trained free of barren plateaus. It is demonstrated that the approximation ratio of QQRA can be close to 1 for complete graphs. To illustrate the effectiveness of QQRA, we compare it with the well known quantum approximate optimization algorithm and the classical Goemans- Williamson algorithm.