Exponential Qubit Reduction in Optimization for Financial Transaction Settlement

Abstract

We extend the qubit-efficient encoding presented in [Tan et al., Quantum 5, 454 (2021)] and apply it to instances of the financial transaction settlement problem constructed from data provided by a regulated financial exchange. Our methods are directly applicable to any QUBO problem with linear inequality constraints. Our extension of previously proposed methods consists of a simplification in varying the number of qubits used to encode correlations as well as a new class of variational circuits which incorporate symmetries, thereby reducing sampling overhead, improving numerical stability and recovering the expression of the cost objective as a Hermitian observable. We also propose optimality-preserving methods to reduce variance in real-world data and substitute continuous slack variables. We benchmark our methods against standard QAOA for problems consisting of 16 transactions and obtain competitive results. Our newly proposed variational ansatz performs best overall. We demonstrate tackling problems with 128 transactions on real quantum hardware, exceeding previous results bounded by NISQ hardware by almost two orders of magnitude.

16 pages, 8 figures

References in corpus (52)

• SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Quantum computational advantage using photons
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• Quantum Circuit Learning
• Strengths and Weaknesses of Quantum Computing
• Predicting Many Properties of a Quantum System from Very Few Measurements
• Parameterized quantum circuits as machine learning models
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• The Variational Quantum Eigensolver: a review of methods and best practices
• Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution
• Practical Quantum Error Mitigation for Near-Future Applications
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• Training variational quantum algorithms is NP-hard
• An initialization strategy for addressing barren plateaus in parametrized quantum circuits
• Layerwise learning for quantum neural networks
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Warm-starting quantum optimization
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Effect of barren plateaus on gradient-free optimization
• Improving Variational Quantum Optimization using CVaR
• Structure optimization for parameterized quantum circuits
• Optimal Quantum Measurements of Expectation Values of Observables
• Sequential minimal optimization for quantum-classical hybrid algorithms
• Increasing the representation accuracy of quantum simulations of chemistry without extra quantum resources
• Variational Quantum Eigensolver with Fewer Qubits
• Solving the sampling problem of the Sycamore quantum circuits
• Efficient tensor network simulation of IBM's Eagle kicked Ising experiment
• Entanglement Devised Barren Plateau Mitigation
• A Non-Orthogonal Variational Quantum Eigensolver
• Parameter Concentration in Quantum Approximate Optimization
• Quantum Power Method by a Superposition of Time-Evolved States
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem
• Error mitigation via verified phase estimation
• Quantum Algorithms for Mixed Binary Optimization applied to Transaction Settlement
• Quantum inverse iteration algorithm for programmable quantum simulators
• Iterative Quantum Assisted Eigensolver
• Overhead for simulating a non-local channel with local channels by quasiprobability sampling
• Computational speedups using small quantum devices
• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Qubit-efficient encoding scheme for quantum simulations of electronic structure
• Qubit-efficient encoding schemes for binary optimisation problems
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Generalization of the output of variational quantum eigensolver by parameter interpolation with low-depth ansatz
• Warm-Starting and Quantum Computing: A Systematic Mapping Study
• Extremal eigenvalues of local Hamiltonians
• Multi-round QAOA and advanced mixers on a trapped-ion quantum computer
• QAOA with $N\cdot p\ge 200$

Cited by in corpus (3)

• Towards large-scale quantum optimization solvers with few qubits
• Resource-Efficient Hadamard Test Tailored Variational Framework for Nonlinear Dynamics on Quantum Computers
• Qubit-efficient quantum combinatorial optimization solver