An Adaptive Mixer Allocation Algorithm for the Quantum Alternating Operator Ansatz

• URL: http://arxiv.org/abs/2412.19621v1
• Date: Fri, 27 Dec 2024 12:43:36 GMT
• Title: An Adaptive Mixer Allocation Algorithm for the Quantum Alternating Operator Ansatz
• Authors: Xiao-Hui Ni, Yu-Sen Wu, Bin-Bin Cai, Wen-Min Li, Su-Juan Qin, Fei Gao,
• Abstract summary: We propose the adaptive mixer allocation algorithm (AMA) to solve constrained optimization problems. AMA significantly reduces the resource consumption, achieving only $34.08%$ ($29.77%$) of QAOA+ circuit depth and $15.05%$ ($18.72%$) of the number of CNOT gates, respectively.
• Score: 2.7704630812545474
• License:
• Abstract: Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thus reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may require substantial gates and circuit depth when the mixer is applied to all qubits in each layer, and the implementation cost of the mixer is high. To address these challenges, we propose the adaptive mixer allocation (AMA) algorithm. AMA constructs a feasible space by selectively applying the mixer to partial qubits in each layer based on the evolution of the optimization process. The performance of AMA in solving the maximum independent set (MIS) problem is investigated. Numerical simulation results demonstrate that, under the same number of optimization runs, AMA achieves a higher optimal approximation ratio--$1.82\%$ ($3.02\%$) higher than QAOA+ on ER (3-regular) graphs. Additionally, AMA significantly reduces the resource consumption, achieving only $34.08\%$ ($29.77\%$) of QAOA+ circuit depth and $15.05\%$ ($18.72\%$) of the number of CNOT gates, respectively, on ER (3-regular) graphs. These results highlight the ability of AMA to enhance computational efficiency and solution quality, making it particularly valuable for resource-constrained quantum devices.

Related papers

• MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
  Quantum Approximate Optimization Algorithm (QAOA) and its variants exhibit immense potential in tackling optimization challenges. The requisite circuit depth for satisfactory performance is problem-specific and often exceeds the maximum capability of current quantum devices. We introduce the Mixer Generator Network (MG-Net), a unified deep learning framework adept at dynamically formulating optimal mixer Hamiltonians.
  arXiv  Detail & Related papers  (2024-09-27T12:28:18Z)
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
  In this work, an implementation of the QAOA2 method for the scalable solution of the MaxCut problem is presented. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation.
  arXiv  Detail & Related papers  (2024-06-25T09:02:31Z)
• Performance Upper Bound of Grover-Mixer Quantum Alternating Operator Ansatz [3.5023108034606256]
  The Quantum Alternating Operator Ansatz (QAOA) represents a branch of quantum algorithms for solving optimization problems. A specific variant, the Grover-Mixer Quantum Alternating Operator Ansatz (GM-QAOA), ensures uniform amplitude across states that share equivalent objective values. We show that the GM-QAOA provides a quadratic enhancement in sampling probability and requires circuit depth that scales exponentially with problem size to maintain consistent performance.
  arXiv  Detail & Related papers  (2024-05-06T05:47:27Z)
• Variational quantum algorithm-preserving feasible space for solving the uncapacitated facility location problem [3.3682090109106446]
  We propose the Variational Quantum Algorithm-Preserving Feasible Space (VQA-PFS) ansatz. This ansatz applies mixed operators on constrained variables while employing Hardware-Efficient Ansatz (HEA) on unconstrained variables. The numerical results demonstrate that VQA-PFS significantly enhances the success probability and exhibits faster convergence.
  arXiv  Detail & Related papers  (2023-12-12T01:36:49Z)
• 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)
• 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)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Threshold-Based Quantum Optimization [0.0]
  Th-QAOA (pronounced Threshold QAOA) is a variation of the Quantum Alternating Operator Ansatz (QAOA) 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.
  arXiv  Detail & Related papers  (2021-06-25T19:36:49Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Grover Mixers for QAOA: Shifting Complexity from Mixer Design to State Preparation [0.0]
  We propose a variation of the Quantum Alternating Operator Ansatz (QAOA) that uses Grover-like selective phase shift mixing operators. GM-QAOA works on any NP optimization problem for which it is possible to efficiently prepare an equal superposition of all feasible solutions.
  arXiv  Detail & Related papers  (2020-05-30T20:24:53Z)

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.