Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study

• URL: http://arxiv.org/abs/2202.06782v1
• Date: Mon, 14 Feb 2022 15:00:28 GMT
• Title: Wasserstein Solution Quality and the Quantum Approximate Optimization Algorithm: A Portfolio Optimization Case Study
• Authors: Jack S. Baker and Santosh Kumar Radha
• Abstract summary: optimizing a portfolio of financial assets is a critical industrial problem which can be approximately solved using algorithms suitable for quantum processing units (QPUs) We benchmark the success of this approach using the Quantum Approximate Optimization Algorithm (QAOA); an algorithm targeting gate-model QPUs. Our focus is on the quality of solutions achieved as determined by the Normalized and Complementary Wasserstein Distance, $eta$.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Optimizing of a portfolio of financial assets is a critical industrial problem which can be approximately solved using algorithms suitable for quantum processing units (QPUs). We benchmark the success of this approach using the Quantum Approximate Optimization Algorithm (QAOA); an algorithm targeting gate-model QPUs. Our focus is on the quality of solutions achieved as determined by the Normalized and Complementary Wasserstein Distance, $\eta$, which we present in a manner to expose the QAOA as a transporter of probability. Using $\eta$ as an application specific benchmark of performance, we measure it on selection of QPUs as a function of QAOA circuit depth $p$. At $n = 2$ (2 qubits) we find peak solution quality at $p=5$ for most systems and for $n = 3$ this peak is at $p=4$ on a trapped ion QPU. Increasing solution quality with $p$ is also observed using variants of the more general Quantum Alternating Operator Ans\"{a}tz at $p=2$ for $n = 2$ and $3$ which has not been previously reported. In identical measurements, $\eta$ is observed to be variable at a level exceeding the noise produced from the finite number of shots. This suggests that variability itself should be regarded as a QPU performance benchmark for given applications. While studying the ideal execution of QAOA, we find that $p=1$ solution quality degrades when the portfolio budget $B$ approaches $n/2$ and increases when $B \approx 1$ or $n-1$. This trend directly corresponds to the binomial coefficient $nCB$ and is connected with the recently reported phenomenon of reachability deficits. Derivative-requiring and derivative-free classical optimizers are benchmarked on the basis of the achieved $\eta$ beyond $p=1$ to find that derivative-free optimizers are generally more effective for the given computational resources, problem sizes and circuit depths.

Related papers

• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
  We experimentally test how existing quantum processing units (QPUs) perform as subsolvers within a multilevel strategy. We find approximate solutions to $10$ instances of fully connected $82$-qubit Sherrington-Kirkpatrick graphs. We observe that quantum optimization results are competitive regarding the quality of solutions compared to classicals.
  arXiv  Detail & Related papers  (2024-08-14T20:06:32Z)
• Computational Supremacy of Quantum Eigensolver by Extension of Optimized Binary Configurations [0.0]
  We develop a quantum eigensolver based on a D-Wave Quantum Annealer (D-Wave QA) This approach performs iterative QA measurements to optimize the eigenstates $vert psi rangle$ without the derivation of a classical computer. We confirm that the proposed QE algorithm provides exact solutions within the errors of $5 times 10-3$.
  arXiv  Detail & Related papers  (2024-06-05T15:19:53Z)
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping [3.47862118034022]
  Noise-Directed Remapping (NDAR) is a algorithm for approximately solving binary optimization problems by leveraging certain types of noise. We consider access to a noisy quantum processor with dynamics that features a global attractor state. Our algorithm bootstraps the noise attractor state by iteratively gauge-transforming the cost-function Hamiltonian in a way that transforms the noise attractor into higher-quality solutions.
  arXiv  Detail & Related papers  (2024-04-01T18:28:57Z)
• 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)
• 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)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  We perform classical simulations of the 127-qubit kicked Ising model, which was recently emulated using a quantum circuit with error mitigation. Our approach is based on the projected entangled pair operator (PEPO) in the Heisenberg picture. We develop a Clifford expansion theory to compute exact expectation values and use them to evaluate algorithms.
  arXiv  Detail & Related papers  (2023-08-06T10:24:23Z)
• Alleviating the quantum Big-$M$ problem [0.237499051649312]
  Classically known as the "Big-$M$" problem, it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks.
  arXiv  Detail & Related papers  (2023-07-19T18:00:05Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45: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)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)

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.