Efficient measure for the expressivity of variational quantum algorithms

Abstract

The superiority of variational quantum algorithms (VQAs) such as quantum neural networks (QNNs) and variational quantum eigen-solvers (VQEs) heavily depends on the expressivity of the employed ansatze. Namely, a simple ansatze is insufficient to capture the optimal solution, while an intricate ansatze leads to the hardness of the trainability. Despite its fundamental importance, an effective strategy of measuring the expressivity of VQAs remains largely unknown. Here, we exploit an advanced tool in statistical learning theory, i.e., covering number, to study the expressivity of VQAs. In particular, we first exhibit how the expressivity of VQAs with an arbitrary ansatze is upper bounded by the number of quantum gates and the measurement observable. We next explore the expressivity of VQAs on near-term quantum chips, where the system noise is considered. We observe an exponential decay of the expressivity with increasing circuit depth. We also utilize the achieved expressivity to analyze the generalization of QNNs and the accuracy of VQE. We numerically verify our theory employing VQAs with different levels of expressivity. Our work opens the avenue for quantitative understanding of the expressivity of VQAs.

arXiv commentUpdated version. Published on PRL

References in corpus (50)

• Quantum Computing in the NISQ era and beyond
• Quantum Machine Learning
• A variational eigenvalue solver on a quantum processor
• Variational Quantum Algorithms
• 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
• Quantum computational chemistry
• Quantum Circuit Learning
• Quantum Chemistry in the Age of Quantum Computing
• Parameterized quantum circuits as machine learning models
• Cost Function Dependent Barren Plateaus in Shallow Parametrized Quantum Circuits
• Evaluating analytic gradients on quantum hardware
• Fermionic quantum computation
• The power of quantum neural networks
• Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms
• Quantum Computational Supremacy
• Noise-Induced Barren Plateaus in Variational Quantum Algorithms
• Hartree-Fock on a superconducting qubit quantum computer
• Efficient Learning for Deep Quantum Neural Networks
• Connecting ansatz expressibility to gradient magnitudes and barren plateaus
• Hybrid quantum-classical algorithms and quantum error mitigation
• Quantum Natural Gradient
• Robust data encodings for quantum classifiers
• Random Quantum Circuits are Approximate 2-designs
• The Expressive Power of Parameterized Quantum Circuits
• Towards Quantum Machine Learning with Tensor Networks
• Experimental Quantum Generative Adversarial Networks for Image Generation
• Information-theoretic bounds on quantum advantage in machine learning
• Quantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space
• Error-mitigated digital quantum simulation
• Learning-based quantum error mitigation
• Training of Quantum Circuits on a Hybrid Quantum Computer
• Stochastic gradient descent for hybrid quantum-classical optimization
• Generalization in Quantum Machine Learning: a Quantum Information Perspective
• Decoding quantum errors with subspace expansions
• Expressibility of the alternating layered ansatz for quantum computation
• Spectral Bias and Task-Model Alignment Explain Generalization in Kernel Regression and Infinitely Wide Neural Networks
• Mitigating realistic noise in practical noisy intermediate-scale quantum devices
• Information Scrambling in Quantum Neural Networks
• Mitigating Coherent Noise Using Pauli Conjugation
• On the statistical complexity of quantum circuits
• Dimensional Expressivity Analysis of Parametric Quantum Circuits
• Toward Trainability of Quantum Neural Networks
• Expressivity of Quantum Neural Networks
• A Grover-search Based Quantum Learning Scheme for Classification
• Pseudo-dimension of quantum circuits
• How often is a random quantum state k-entangled?
• Experimental realization of a quantum image classifier via tensor-network-based machine learning
• Fundamental limitations for measurements in quantum many-body systems

Cited by in corpus (24)

• Generalization in quantum machine learning from few training data
• Quantum circuit architecture search for variational quantum algorithms
• Recent advances for quantum classifiers
• Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks
• Out-of-distribution generalization for learning quantum dynamics
• Subtleties in the trainability of quantum machine learning models
• Analytic theory for the dynamics of wide quantum neural networks
• Mitigating Barren Plateaus with Transfer-learning-inspired Parameter Initializations
• Quantum Phase Recognition via Quantum Kernel Methods
• Structural risk minimization for quantum linear classifiers
• Dynamical simulation via quantum machine learning with provable generalization
• Exponential data encoding for quantum supervised learning
• Quantum Computing Techniques for Multi-Knapsack Problems
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Explaining Quantum Circuits with Shapley Values: Towards Explainable Quantum Machine Learning
• On exploring the potential of quantum auto-encoder for learning quantum systems
• Expressivity of Variational Quantum Machine Learning on the Boolean Cube
• Characterization of variational quantum algorithms using free fermions
• The dilemma of quantum neural networks
• Quantum computing quantum Monte Carlo algorithm
• Encoding-dependent generalization bounds for parametrized quantum circuits
• Learning Fourier series with parametrized quantum circuits
• Accelerating variational quantum algorithms with multiple quantum processors
• Quantum Machine Learning with SQUID