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
- 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) - Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming [0.0]
In this work, we integrate the potentials of quantum and classical techniques for optimization.
We reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size.
We present numerous computational results from real quantum hardware.
arXiv Detail & Related papers (2023-02-10T20:12:53Z) - 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) - 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) - 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) - Second-order Conditional Gradient Sliding [79.66739383117232]
We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm.
The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations.
It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
arXiv Detail & Related papers (2020-02-20T17:52:18Z)
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.