Variational quantum algorithm-preserving feasible space for solving the uncapacitated facility location problem

• URL: http://arxiv.org/abs/2312.06922v4
• Date: Thu, 11 Jan 2024 01:40:28 GMT
• Title: Variational quantum algorithm-preserving feasible space for solving the uncapacitated facility location problem
• Authors: Sha-Sha Wang, Hai-Ling Liu, Yong-Mei Li, Fei Gao, Su-Juan Qin, and Qiao-Yan Wen
• Abstract summary: 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.
• Score: 3.3682090109106446
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quantum Alternating Operator Ansatz (QAOA+) is one of the Variational Quantum Algorithm (VQA) specifically developed to tackle combinatorial optimization problems by exploring the feasible space in search of a target solution. For constrained optimization problems with unconstrained variables, which we call Unconstrained-Variables Problems (UVPs), the mixed operators in the QAOA+ circuit are applied to the constrained variables, while the single-qubit rotating gates $R_X$ operate on the unconstrained variables. The expressibility of this circuit is limited by the shortage of two-qubit gates and the parameter sharing in the $R_X$, which consequently impacts the performance of QAOA+ for solving UVPs. Therefore, it is crucial to develop a suitable ansatz for UVPs. In this paper, we propose the Variational Quantum Algorithm-Preserving Feasible Space (VQA-PFS) ansatz, exemplified by the Uncapacitated Facility Location Problem (UFLP), that 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 compared to QAOA+, Quantum Approximation Optimization Algorithm (QAOA), and HEA. Furthermore, VQA-PFS reduces the circuit depth dramatically in comparison to QAOA+ and QAOA. Our algorithm is general and instructive in tackling UVPs.

Related papers

• 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)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Variational Quantum Eigensolver with Constraints (VQEC): Solving Constrained Optimization Problems via VQE [0.0]
  Variational quantum approaches have shown great promise in finding near-optimal solutions to computationally challenging tasks. This work proposes a hybrid quantum-classical algorithmic paradigm termed VQEC to handle optimization with constraints.
  arXiv  Detail & Related papers  (2023-11-14T19:49:09Z)
• Post-processing variationally scheduled quantum algorithm for constrained combinatorial optimization problems [6.407238428292173]
  We propose a post-processing variationally scheduled quantum algorithm (pVSQA) for solving constrained optimization problems (COPs) pVSQA combines the variational methods and the post-processing technique. We implement pVSQA on a quantum annealer and a gate-type quantum device.
  arXiv  Detail & Related papers  (2023-09-15T03:09:16Z)
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem [0.0]
  We discuss the Capacitated Vehicle Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP) Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically. Quantum computing may offer a way to improve the time to solution.
  arXiv  Detail & Related papers  (2023-04-19T13:03:50Z)
• Shuffle-QUDIO: accelerate distributed VQE with trainability enhancement and measurement reduction [77.97248520278123]
  We propose Shuffle-QUDIO to involve shuffle operations into local Hamiltonians during the quantum distributed optimization. Compared with QUDIO, Shuffle-QUDIO significantly reduces the communication frequency among quantum processors and simultaneously achieves better trainability.
  arXiv  Detail & Related papers  (2022-09-26T06:51:20Z)
• Iteration Complexity of Variational Quantum Algorithms [5.203200173190989]
  We argue that noise makes evaluations of the objective function via quantum circuits biased. We derive the missing guarantees and find that the rate of convergence is unaffected.
  arXiv  Detail & Related papers  (2022-09-21T19:18:41Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)
• 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)

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.