Quantum Algorithms for Fixed Qubit Architectures

Abstract

Gate model quantum computers with too many qubits to be simulated by available classical computers are about to arrive. We present a strategy for programming these devices without error correction or compilation. This means that the number of logical qubits is the same as the number of qubits on the device. The hardware determines which pairs of qubits can be addressed by unitary operators. The goal is to build quantum states that solve computational problems such as maximizing a combinatorial objective function or minimizing a Hamiltonian. These problems may not fit naturally on the physical layout of the qubits. Our algorithms use a sequence of parameterized unitaries that sit on the qubit layout to produce quantum states depending on those parameters. Measurements of the objective function (or Hamiltonian) guide the choice of new parameters with the goal of moving the objective function up (or lowering the energy). As an example we consider finding approximate solutions to MaxCut on 3-regular graphs whereas the hardware is physical qubits laid out on a rectangular grid. We prove that the lowest depth version of the Quantum Approximate Optimization Algorithm will achieve an approximation ratio of at least 0.5293 on all large enough instances which beats random guessing (0.5). We open up the algorithm to have different parameters for each single qubit $X$ rotation and for each $ZZ$ interaction associated with the nearest neighbor interactions on the grid. Small numerical experiments indicate that an enveloping classical algorithm can be used to find the parameters which sit on the grid to optimize an objective function with a different connectivity. We discuss strategies for finding good parameters but offer no evidence yet that the proposed approach can beat the best classical algorithms. Ultimately the strength of this approach will be determined by running on actual hardware.

20 pages, 6 figures

References in corpus (14)

• A variational eigenvalue solver on a quantum processor
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• Logic gates at the surface code threshold: Superconducting qubits poised for fault-tolerant quantum computing
• Characterizing Quantum Supremacy in Near-Term Devices
• Demonstration of a small programmable quantum computer with atomic qubits
• Towards Practical Quantum Variational Algorithms
• Detecting arbitrary quantum errors via stabilizer measurements on a sublattice of the surface code
• Realization of a scalable Shor algorithm
• Average-case complexity versus approximate simulation of commuting quantum computations
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Practical optimization for hybrid quantum-classical algorithms
• Impossibility of Classically Simulating One-Clean-Qubit Computation

Cited by in corpus (32)

• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Supervised learning with quantum enhanced feature spaces
• Barren plateaus in quantum neural network training landscapes
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum machine learning: a classical perspective
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Differentiable Learning of Quantum Circuit Born Machine
• Warm-starting quantum optimization
• Structure optimization for parameterized quantum circuits
• $XY$-mixers: analytical and numerical results for QAOA
• Efficient variational simulation of non-trivial quantum states
• Compiling quantum circuits to realistic hardware architectures using temporal planners
• Learning and Inference on Generative Adversarial Quantum Circuits
• Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
• Quantum-enhanced data classification with a variational entangled sensor network
• Training Optimization for Gate-Model Quantum Neural Networks
• Evaluation of QAOA based on the approximation ratio of individual samples
• Quantum Approximate Optimization Algorithm with Adaptive Bias Fields
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Quantum State Optimization and Computational Pathway Evaluation for Gate-Model Quantum Computers
• Entanglement Accessibility Measures for the Quantum Internet
• End-to-End Quantum Machine Learning Implemented with Controlled Quantum Dynamics
• Quantum Kitchen Sinks: An algorithm for machine learning on near-term quantum computers
• Analytical Framework for Quantum Alternating Operator Ansätze
• Shortcuts to Quantum Approximate Optimization Algorithm
• Networked Quantum Services
• Theory of Noise-Scaled Stability Bounds and Entanglement Rate Maximization in the Quantum Internet
• Mixer-Phaser Ansätze for Quantum Optimization with Hard Constraints
• Correlation Measure Equivalence in Dynamic Causal Structures of Quantum Gravity
• Small quantum computers and large classical data sets
• Using machine learning for quantum annealing accuracy prediction