In variational quantum optimization methods, the manner in which classical data are embedded into the quantum circuit significantly influences the representational capacity and solution behavior of the model. In the literature, this aspect is generally considered a secondary component. In this study, the effect of a threshold-based adaptive quantum encoding approach is analyzed using the NP-hard max-cut problem. The proposed method transforms normalized node-based features into quantum rotations through a data-sensitive angle mapping governed by a threshold value. Experimental results indicate that the adaptive encoding variant with a global threshold value of$(\mathbf{t}=\mathbf{0. 7 5})$achieves a higher performance in terms of the average approximation ratio compared to standard encoding methods. These findings demonstrate that input encoding should be considered a critical modeling component in variational quantum optimization.
In variational quantum optimization methods, the manner in which classical data are embedded into the quantum circuit significantly influences the representational capacity and solution behavior of the model. In the literature, this aspect is generally considered a secondary component. In this study, the effect of a threshold-based adaptive quantum encoding approach is analyzed using the NP-hard max-cut problem. The proposed method transforms normalized node-based features into quantum rotations through a data-sensitive angle mapping governed by a threshold value. Experimental results indicate that the adaptive encoding variant with a global threshold value of(t=0.75)achieves a higher performance in terms of the average approximation ratio compared to standard encoding methods. These findings demonstrate that input encoding should be considered a critical modeling component in variational quantum optimization.
We propose and study Th-QAOA (pronounced Threshold QAOA), a variation of the Quantum Alternating Operator Ansatz (QAOA) that replaces the standard phase separator operator, which encodes the objective function, with a threshold function that returns a value 1 for solutions with an objective value above the threshold and a 0 otherwise. We vary the threshold value to arrive at a quantum optimization algorithm. We focus on a combination with the Grover Mixer operator; the resulting GM-Th-QAOA can be viewed as a generalization of Grover’s quantum search algorithm and its minimum/maximum finding cousin to approximate optimization.Our main findings include: (i) we provide intuitive arguments and show empirically that the optimum parameter values of GM-Th-QAOA (angles and threshold value) can be found with O(log(p) × log M) iterations of the classical outer loop, where p is the number of QAOA rounds and M is an upper bound on the solution value (often the number of vertices or edges in an input graph), thus eliminating the notorious outer-loop parameter finding issue of other QAOA algorithms; (ii) GM-Th-QAOA can be simulated classically with little effort up to 100 qubits through a set of tricks that cut down memory requirements; (iii) somewhat surprisingly, GM-Th-QAOA outperforms non-thresholded GM-QAOA in terms of approximation ratios achieved. This third result holds across a range of optimization problems (MaxCut, Max k-VertexCover, Max k-DensestSubgraph, MaxBisection) and various experimental design parameters, such as different input edge densities and constraint sizes.
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 weighted MAX k -CUT problem involves partitioning a weighted undirected graph into k subsets, or colors, to maximize the sum of the weights of edges between vertices in different subsets. This problem has significant applications across multiple domains. This study explores encoding methods for MAX k -CUT on qubit systems by utilizing quantum approximate optimization algorithms (QAOA) and addressing the challenge of encoding integer values on quantum devices with binary variables. We examine various encoding schemes and evaluate the efficiency of these approaches. The study presents a systematic and resource-efficient method to implement the phase separation operator for the cost function of the MAX k -CUT problem. When encoding the problem into the full Hilbert space, we show the importance of encoding the colors in a balanced way. We also explore the option of encoding the problem into a suitable subspace by designing suitable state preparations and constrained mixers (LX- and Grover-mixer). Numerical simulations on weighted and unweighted graph instances demonstrate the effectiveness of these encoding schemes, particularly in optimizing circuit depth, approximation ratios, and computational efficiency.
The MaxCut is a combinatorial problem which belongs to the NP-hard class. The algorithm to solve it can be mapped into a quantum system, where the optimal configuration matches the ground state of a target Hamiltonian. It is possible to implement the adiabatic theorem into the circuit model via the QAOA algorithm, by arbitrarily choosing from both the gate-based and the measurement-based quantum computing (MBQC) settings. Recently, the MaxCut problem has been generalized to the Max K-Cut version also in the MBQC frame, where K stands for the number of cuts to implement. Here, the QAOA algorithm for a Max K-Cut is solved for a graph with arbitrary number of vertices V and number of cuts K scaling as a power of 2, along with the circuit depth p. The problem is solved on a emulator based on classical HPC resources. In order to test the performances of a Max K-cut implemented in the MBQC frame, we report how the average runtime and the approximation ratio scale by increasing V, K and p, comparing the results from two different topologies of graphs, 2-regular graphs with null weights on the diagonals versus the the fully-connected graphs. Eventually, the approximation ratio, evaluated as a parameter of success, is shown to yield optimal performances.
Abstract MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only O(logN) O ( log N ) qubits to tackle graphs of size N , an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.
The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical variational algorithm designed to tackle combinatorial optimization problems that are classically intractable. Careful parameter initialization in QAOA can reduce the number of quantum circuit evaluations required, making it more feasible to run on noisy intermediate-scale quantum (NISQ) devices. In this work, We focus on MaX-Cut, a classic NP-hard optimization problem, and propose a conditional variational autoencoder (CVAE) scheme for generating initial QAOA parameters for the Max-Cut problems based on input graph structures. The CVAE, trained on optimal parameters from 270 ten-node graphs, produces multiple parameter candidates conditioned on 27-dimensional feature vectors that incorporate spectral properties as well as learned embeddings. We evaluate and compare two strategies: direct initialization using the highestconfidence prediction, and dynamic injection which monitors optimization progress and intervenes when needed. On 89 test graphs, the dynamic injection strategy increased successful convergence cases from 41 to 49, reduced mean iteration count by 4.94.