Performance analysis of a filtering variational quantum algorithm

Abstract

Even a minor boost in solving combinatorial optimization problems can greatly benefit multiple industries. Quantum computers, with their unique information processing capabilities, hold promise for delivering such enhancements. The Filtering Variational Quantum Eigensolver (F-VQE) is a variational hybrid quantum algorithm designed to solve combinatorial optimization problems on existing quantum computers with limited qubit number, connectivity, and fidelity. In this work we employ Instantaneous Quantum Polynomial circuits as our parameterized quantum circuits. We propose a hardware-efficient implementation that respects limited qubit connectivity and show that they halve the number of circuits necessary to evaluate the gradient with the parameter-shift rule. To assess the potential of this protocol in the context of combinatorial optimization, we conduct extensive numerical analysis. We compare the performance against three classical baseline algorithms on weighted MaxCut and the Asymmetric Traveling Salesperson Problem (ATSP). We employ noiseless simulators for problems encoded on 13 to 29 qubits, and up to 37 qubits on the IBMQ real quantum devices. The ATSP encoding employed reduces the number of qubits and avoids the need of constraints compared to the standard QUBO / Ising model. Despite some observed positive signs, we conclude that significant development is necessary for a practical advantage with F-VQE.

References in corpus (23)

• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Barren plateaus in quantum neural network training landscapes
• Quantum Circuit Learning
• Parameterized quantum circuits as machine learning models
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• t$|$ket$⟩$ : A Retargetable Compiler for NISQ Devices
• Qulacs: a fast and versatile quantum circuit simulator for research purpose
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Average-case complexity versus approximate simulation of commuting quantum computations
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum Sampling Problems, BosonSampling and Quantum Supremacy
• Focus beyond quadratic speedups for error-corrected quantum advantage
• A case study of variational quantum algorithms for a job shop scheduling problem
• Barren plateaus in quantum tensor network optimization
• Unconstrained Binary Models of the Travelling Salesman Problem Variants for Quantum Optimization
• Robust sparse IQP sampling in constant depth
• Highly Efficient Encoding for Job-Shop Scheduling Problems and its Application on Quantum Computers
• Performance of Uncoded Implementation of Grover's Algorithm on Today's Quantum Processors

Cited by in corpus (1)

• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice