Quasi-binary encoding based quantum alternating operator ansatz

• URL: http://arxiv.org/abs/2304.06915v2
• Date: Wed, 24 Jan 2024 09:36:15 GMT
• Title: Quasi-binary encoding based quantum alternating operator ansatz
• Authors: Bingren Chen, Hanqing Wu, Haomu Yuan, Lei Wu, Xin Li
• Abstract summary: This paper proposes a quasi-binary encoding based algorithm for solving a specific quadratic optimization models with discrete variables. In other parts of the QAOA framework, we also incorporate ideas such as CVaR-QAOA and parameter scheduling methods into our QAOA algorithm.
• Score: 7.681120805934572
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: This paper proposes a quasi-binary encoding based algorithm for solving a specific quadratic optimization models with discrete variables, in the quantum approximate optimization algorithm (QAOA) framework. The quadratic optimization model has three constraints: 1. Discrete constraint, the variables are required to be integers. 2. Bound constraint, each variable is required to be greater than or equal to an integer and less than or equal to another integer. 3. Sum constraint, the sum of all variables should be a given integer. To solve this optimization model, we use quasi-binary encoding to encode the variables. For an integer variable with upper bound $U_i$ and lower bound $L_i$, this encoding method can use at most $2\log_2 (U_i-L_i+1)$ qubits to encode the variable. Moreover, we design a mixing operator specifically for this encoding to satisfy the hard constraint model. In the hard constraint model, the quantum state always satisfies the constraints during the evolution, and no penalty term is needed in the objective function. In other parts of the QAOA framework, we also incorporate ideas such as CVaR-QAOA and parameter scheduling methods into our QAOA algorithm. In the financial field, by introducing precision, portfolio optimization problems can be reduced to the above model. We will use portfolio optimization cases for numerical simulation. We design an iterative method to solve the problem of coarse precision caused by insufficient qubits of the simulators or quantum computers. This iterative method can refine the precision by multiple few-qubit experiments.

Related papers

• QUBO Refinement: Achieving Superior Precision through Iterative Quantum Formulation with Limited Qubits [3.2995359570845912]
  Quantum algorithms are capable of solving linear equations and eigenvalues, surpassing the pace of classical computers. By exploiting this technology, quantum optimization models have been proposed for applications, such as linear systems, eigenvalue problems, RSA cryptosystems, and CT image reconstruction. The accuracies of the existing Qiskit simulator, D-Wave system simulator, and hybrid solver are limited to two decimal places. We propose a new iterative algorithm that sequentially progresses from the highest to the lowest exponent in binarizing each number.
  arXiv  Detail & Related papers  (2024-11-25T06:56:00Z)
• An encoding of argumentation problems using quadratic unconstrained binary optimization [1.104960878651584]
  We develop a way to encode several NP-Complete problems in Abstract Argumentation to Quadratic Unconstrained Binary Optimization problems. With the QUBO formulation, exploiting new computing architectures, such as Quantum and Digital Annealers, is possible. We performed tests to prove the correctness and applicability of classical problems in Argumentation and enforcement of argument sets.
  arXiv  Detail & Related papers  (2024-09-09T11:29:46Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Dual-Matrix Domain-Wall: A Novel Technique for Generating Permutations by QUBO and Ising Models with Quadratic Sizes [0.14454647768189902]
  This paper introduces a novel permutation encoding technique called dual-matrix domain-wall. It significantly reduces the number of quadratic terms and the maximum absolute coefficient values in the kernel. We also demonstrate the applicability of our encoding technique to partial permutations and Quadratic Unconstrained Binary Optimization (QUBO) models.
  arXiv  Detail & Related papers  (2023-08-02T09:15:30Z)
• Discrete quadratic model QUBO solution landscapes [0.0]
  We investigate the effects of choice of encoding and penalty strength on the structure of QUBO DQM solution landscapes. This research focuses specifically on one-hot and domain-wall encodings.
  arXiv  Detail & Related papers  (2023-04-30T20:19:46Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Quantum Sparse Coding [5.130440339897477]
  We develop a quantum-inspired algorithm for sparse coding. The emergence of quantum computers and Ising machines can potentially lead to more accurate estimations. We conduct numerical experiments with simulated data on Lightr's quantum-inspired digital platform.
  arXiv  Detail & Related papers  (2022-09-08T13:00:30Z)
• 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)
• Optimization-based Block Coordinate Gradient Coding for Mitigating Partial Stragglers in Distributed Learning [58.91954425047425]
  This paper aims to design a new gradient coding scheme for mitigating partial stragglers in distributed learning. We propose a gradient coordinate coding scheme with L coding parameters representing L possibly different diversities for the L coordinates, which generates most gradient coding schemes.
  arXiv  Detail & Related papers  (2022-06-06T09:25:40Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)

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.