Unsupervised strategies for identifying optimal parameters in Quantum
Approximate Optimization Algorithm
- URL: http://arxiv.org/abs/2202.09408v2
- Date: Fri, 6 May 2022 17:50:29 GMT
- Title: Unsupervised strategies for identifying optimal parameters in Quantum
Approximate Optimization Algorithm
- Authors: Charles Moussa, Hao Wang, Thomas B\"ack, Vedran Dunjko
- Abstract summary: We study unsupervised Machine Learning approaches for setting parameters without optimization.
We showcase them within Recursive-QAOA up to depth $3$ where the number of QAOA parameters used per iteration is limited to $3$.
We obtain similar performances to the case where we extensively optimize the angles, hence saving numerous circuit calls.
- Score: 3.508346077709686
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As combinatorial optimization is one of the main quantum computing
applications, many methods based on parameterized quantum circuits are being
developed. In general, a set of parameters are being tweaked to optimize a cost
function out of the quantum circuit output. One of these algorithms, the
Quantum Approximate Optimization Algorithm stands out as a promising approach
to tackling combinatorial problems. However, finding the appropriate parameters
is a difficult task. Although QAOA exhibits concentration properties, they can
depend on instances characteristics that may not be easy to identify, but may
nonetheless offer useful information to find good parameters. In this work, we
study unsupervised Machine Learning approaches for setting these parameters
without optimization. We perform clustering with the angle values but also
instances encodings (using instance features or the output of a variational
graph autoencoder), and compare different approaches. These angle-finding
strategies can be used to reduce calls to quantum circuits when leveraging QAOA
as a subroutine. We showcase them within Recursive-QAOA up to depth $3$ where
the number of QAOA parameters used per iteration is limited to $3$, achieving a
median approximation ratio of $0.94$ for MaxCut over $200$ Erd\H{o}s-R\'{e}nyi
graphs. We obtain similar performances to the case where we extensively
optimize the angles, hence saving numerous circuit calls.
Related papers
- Symmetry-preserved cost functions for variational quantum eigensolver [0.0]
Hybrid quantum-classical variational algorithms are considered ideal for noisy quantum computers.
We propose encoding symmetry preservation directly into the cost function, enabling more efficient use of Hardware-Efficient Ans"atze.
arXiv Detail & Related papers (2024-11-25T20:33:47Z) - 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) - Graph Representation Learning for Parameter Transferability in Quantum Approximate Optimization Algorithm [1.0971022294548696]
The quantum approximate optimization algorithm (QAOA) is one of the most promising candidates for achieving quantum advantage through quantum-enhanced optimization.
In this work, we apply five different graph embedding techniques to determine good donor candidates for parameter transferability.
Using this technique, we effectively reduce the number of iterations required for parameter optimization, obtaining an approximate solution to the target problem with an order of magnitude speedup.
arXiv Detail & Related papers (2024-01-12T16:01:53Z) - Trainability Analysis of Quantum Optimization Algorithms from a Bayesian
Lens [2.9356265132808024]
We show that a noiseless QAOA circuit with a depth of $tildemathtlog nright)$ can be trained efficiently.
Our results offer theoretical performance of quantum algorithms in the noisy intermediate-scale quantum era.
arXiv Detail & Related papers (2023-10-10T02:56:28Z) - 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) - 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) - Progress towards analytically optimal angles in quantum approximate
optimisation [0.0]
The Quantum Approximate optimisation algorithm is a $p$ layer, time-variable split operator method executed on a quantum processor.
We prove that optimal parameters for $p=1$ layer reduce to one free variable and in the thermodynamic limit, we recover optimal angles.
We moreover demonstrate that conditions for vanishing gradients of the overlap function share a similar form which leads to a linear relation between circuit parameters, independent on the number of qubits.
arXiv Detail & Related papers (2021-09-23T18:00:13Z) - Parameters Fixing Strategy for Quantum Approximate Optimization
Algorithm [0.0]
We propose a strategy to give high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths.
We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erd"os-R'enyi graphs.
arXiv Detail & Related papers (2021-08-11T15:44:16Z) - 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) - Cross Entropy Hyperparameter Optimization for Constrained Problem
Hamiltonians Applied to QAOA [68.11912614360878]
Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications.
Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem.
In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
arXiv Detail & Related papers (2020-03-11T13:52:41Z)
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.