Encodings of the weighted MAX k-CUT on qubit systems

• URL: http://arxiv.org/abs/2411.08594v3
• Date: Wed, 20 Nov 2024 12:00:55 GMT
• Title: Encodings of the weighted MAX k-CUT on qubit systems
• Authors: Franz G. Fuchs, Ruben P. Bassa, Frida Lien,
• Abstract summary: This paper explores encoding methods for the weighted MAX k-CUT problem on qubit systems. We examine various encoding schemes and evaluate the efficiency of these approaches. Numerical simulations on weighted and unweighted graph instances demonstrate the effectiveness of these encoding schemes.
• Score: 0.0
• License:
• Abstract: The weighted MAX k-CUT problem involves partitioning a weighted undirected graph into k subsets to maximize the sum of the weights of edges between vertices in different subsets. This problem has significant applications across multiple domains. This paper explores encoding methods for MAX k-CUT on qubit systems, 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 paper presents a systematic and resource efficient method to implement phase separation for diagonal square binary matrices. When encoding the problem into the full Hilbert space, we show the importance of balancing the "bin sizes". We also explore the option to encode 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.

Related papers

• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem [2.4968861883180447]
  Finding ground state solutions of diagonal Hamiltonians is relevant for both theoretical as well as practical problems of interest in many domains such as finance, physics and computer science. Here we use imaginary time evolution through a new block encoding scheme to obtain the ground state of such problems and apply our method to MaxCut as an illustration.
  arXiv  Detail & Related papers  (2024-11-16T08:17:36Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Quantum Approximate Optimization Algorithm with Cat Qubits [0.0]
  We numerically simulate solving MaxCut problems using QAOA with cat qubits. We show that running QAOA with cat qubits increases the approximation ratio for random instances of MaxCut with respect to qubits encoded into two-level systems.
  arXiv  Detail & Related papers  (2023-05-09T15:44:52Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• An entanglement perspective on the quantum approximate optimization algorithm [0.0]
  We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits. We also investigate the entanglement spectrum in connection with random matrix theory.
  arXiv  Detail & Related papers  (2022-06-14T17:37:44Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Quantum approximate optimization algorithm for qudit systems [0.0]
  We discuss the quantum approximate optimization algorithm (QAOA) for qudit systems. We illustrate how the QAOA can be used to formulate a variety of integer optimization problems. We present numerical results for a charging optimization problem mapped onto a max-$k$-graph coloring problem.
  arXiv  Detail & Related papers  (2022-04-01T10:37:57Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)
• Efficient encoding of the weighted MAX k-CUT on a quantum computer using QAOA [0.0]
  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. The new formulation uses a binary encoding that requires only |V|log_2(k) qubits.
  arXiv  Detail & Related papers  (2020-09-02T14:15:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.