PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient measure for the expressivity of variational quantum algorithms

Yuxuan Du, Zhuozhuo Tu, Xiao Yuan, Dacheng Tao

arXiv:2104.09961v2quant-ph

TL;DR

Measuring VQA expressivity is important because ansatze that are too simple may miss target concepts, while more expressive ansatze can be harder to train. The paper uses covering numbers to bound expressivity in terms of circuit and observable properties and examines noisy settings. Its results connect expressivity to QNN generalization and show that noise does not increase expressivity relative to the ideal case.

  • Problem

    An effective way to measure VQA expressivity is lacking, despite its relevance to choosing hypothesis spaces that can approximate target concepts.

    Source: pp. 1–2

  • Method

    The paper uses covering numbers to bound VQA hypothesis-space expressivity using gate count, gate arity, qudit dimension, and observable norm, then extends the analysis to noisy circuits.

    Source: pp. 1–2

  • Results

    The bounds make gate count and gate type decisive expressivity factors, while quantum noise cannot increase expressivity over the ideal case and depolarization noise shrinks it.

    Source: p. 3

  • Takeaways & Limitations

    With fixed qudit dimension and observable norm, VQA expressivity can be compared and controlled by tuning the number and arity of trainable gates.

    Source: p. 1

    The stated noise analysis includes a depolarization-noise setting.

    Source: p. 4

Abstract

from arXiv · show

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.

Appendix A: Proof of Theorem 1

The proof bounds the hypothesis-space covering number by transferring a cover between metric spaces and controlling how circuit approximation changes the measured hypothesis. It derives a Lipschitz constant for this transfer and combines it with a cover of the circuit operators.

Appendix A: Proof of Theorem 1

  • The circuit-covering lemma considers N-qudit ansatze with Ng gates, at most k qudits per gate, and Ngt trainable gates.The proof uses the operator norm when measuring distances between circuit operators.Source: Appendix A · p. 9
  • The proof obtains the hypothesis-space covering bound by combining a metric-space covering-number comparison with a cover of the circuit operators.The comparison applies to two metric spaces linked by a bi-Lipschitz map, subject to the stated radius condition.Source: Appendix A · p. 9
  • Approximating the circuit gates yields Lipschitz constant K = 1, which the proof combines with the covering lemmas to bound the hypothesis-space covering number.The proof first relates the measured-hypothesis distance to the circuit distance, then applies Lemma 1 and Lemma 2.Source: Appendix A · pp. 9–10

1. Proof of Lemma 2

The proof bounds the operator-group covering number by constructing circuit approximations from a cover of the possible trainable gates. It controls the resulting operator discrepancy and transfers the gate-level cover to the operator group.

1. Proof of Lemma 2

  • The proof targets the operator group Hcirc formed by conjugating the observable with the trainable circuit, which contains Ngt trainable and Ng − Ngt fixed gates.It constructs approximating circuits by replacing each trainable gate with a nearby element of a fixed cover.Source: §1 · p. 10
  • Replacing each trainable gate by its nearest cover element bounds the circuit discrepancy by Ngt times the gate-level approximation error.The proof then bounds the observable-conjugation discrepancy using the triangle inequality and the operator norm of O.Source: §1 · p. 10
  • The constructed set is an Ngt∥O∥ϵ-cover of Hcirc, yielding the operator-group covering bound used in the theorem proof.The gate-level cover is for the unitary group U(d^k) under operator-norm distance.Source: §1 · p. 10

Appendix B: Proof of Proposition 1

The proof treats a general noisy channel and then specializes to local depolarization noise. In each case, it relates output discrepancies to circuit discrepancies to obtain a covering-number bound.

Appendix B: Proof of Proposition 1

  • The argument proceeds in two stages: first bounding the covering number for a general noisy channel, then specializing the analysis to depolarization noise.Source: Appendix B · p. 11
  • For a general quantum channel, the proof uses channel contractivity and rank-one circuit states to establish the relation needed to transfer the circuit cover to the noisy hypothesis space.It derives the relevant constant K before applying Lemma 2 to bound the noisy covering number.Source: Appendix B · p. 11
  • The proof separately considers local depolarization applied at each gate and uses the depolarization property to derive the approximation factor for this setting.It then applies Lemma 2 to upper-bound the covering number under depolarization noise.Source: Appendix B · pp. 11–12

Appendix C: Proof of Theorem 2

The proof derives a QNN generalization bound by bounding Rademacher complexity through covering numbers. Its stated assumptions include a Lipschitz, bounded loss and a finite sample.

Appendix C: Proof of Theorem 2

  • The stated bound assumes the loss is L1-Lipschitz and upper bounded by C1, with probability taken over a sample of size n.Source: Appendix C · p. 12
  • The proof uses Dudley’s entropy integral to connect Rademacher complexity with covering numbers.It first bounds the covering number of the sample-wise hypothesis vectors using covers of their values on individual examples.Source: Appendix C · p. 12
  • The theorem gives a probability-1 − δ generalization bound for QNNs by combining the loss-based bound with the derived Rademacher-complexity bound.The result applies under the stated loss assumptions and sample size n.Source: Appendix C · pp. 12–13

Appendix D: Expressivity of other advanced quantum neural networks

The appendix applies the paper’s covering-number framework to hardware-efficient and tensor-network QNN ansätze. It specifies circuit constructions and gives expressivity bounds for these architectures.

Ansatz illustrations

  • Figure D.5 distinguishes the tensor-network QNN constructions by showing the matrix-product-state structure on the left and the tree structure on the right.Figure E.6 separately depicts a 7-qubit hardware-efficient ansatz and the QNN implementation used in simulation.Source: Figure D.5 · p. 14, Figure E.6 · p. 15

Hardware-efficient Ansätze

  • With depolarization, the hardware-efficient QNN covering number is bounded by (1 − p)^(4NL)(21NL∥O∥/ϵ)^(6NL), versus (21NL∥O∥/ϵ)^(6NL) ideally.The architecture has L repeated layers, each with parameterized single-qubit gates and fixed two-qubit gates; the stated general setting uses three parameters per single-qubit gate and N two-qubit gates per layer.Source: Appendix D · pp. 13–14

Tensor-network Ansätze

  • For the matrix-product-state ansatz, each layer acts on M1 qubits, with maximum depth ⌈N/(M1 − 1)⌉ and assumed local gate counts of 3M1 single-qubit and M1 two-qubit gates.The appendix applies Theorem 1 and Proposition 1 to quantify its expressivity, but the supplied bound is incomplete.Source: Appendix D · p. 14
  • For the tree-structured tensor-network ansatz, the involved number of quantum gates is intuitively exponentially decreased in terms of l ∈ [L]; the local unitary with l = 1 contains six single-qubit gates and one two-qubit gate.Source: Appendix D · pp. 14–15

Appendix E: Numerical simulation details of QNN

The appendix details a noisy-QNN simulation on a synthetic binary dataset, including its encoding, training split, and depolarization settings. Both training and test accuracy decline as depolarization increases, reaching about 50% at p = 0.9.

Data construction

  • Classical data are loaded into quantum form using qubit encoding, and each example has seven features in [0, 2π)^7 with a binary label.The dataset construction imitates studies.Source: Appendix E · p. 15
  • The synthetic dataset has 400 equally distributed binary examples, split into 60 training examples and 340 test examples.Each input has seven features, and the target concept is constructed to be covered by the QNN hypothesis space when L ≥ 2.Source: Appendix E · pp. 15–16

Hyper-parameters

  • Training uses batch gradient descent with batch size 4 and learning rate 0.2, with the training set shuffled each epoch.Source: Appendix E · p. 16

Noisy-QNN simulation

  • At p = 0.9, noisy-QNN learning performance is around 50%, no better than random guess, while training and test accuracies decline as depolarization increases.The simulation uses a hardware-efficient ansatz with L = 2 and tests p ∈ {0.1, 0.5, 0.9}, repeating each setting five times.Source: Appendix E · p. 16

Appendix F: Proof of Corollary 1

This appendix introduces UCCSD and uses its gate-count scaling to derive Corollary 1. UCCSD truncates unitary coupled-cluster excitation operators to single and double excitations.

UCCSD

  • UCCSD truncates unitary coupled-cluster excitation operators to single and double excitations, approximating T by T1 + T2.It is described as useful for accurately describing many molecular systems and exact for systems with two electrons.Source: Appendix F · pp. 16–17

Gate complexity

  • For Bravyi-Kitaev and Jordan-Wigner transformations, the number of gates required to implement UCCSD is bounded by Ng ∼ O(N^5).Source: Appendix F · p. 17

Proof of Corollary 1

  • Corollary 1 follows by substituting the UCCSD gate-count scaling into Theorem 2 and Proposition 1.Source: Appendix F · p. 17

Appendix G: Numerical simulation details of VQE

With Adam, the modest-expressivity VQE performs better than the overwhelming-expressivity ansatz, and performance degrades as layer count increases. The appendix describes the ansätze, molecular Hamiltonian, and optimization settings used in these simulations.

Ansatz implementation

  • The restricted ansatz contains one trainable gate, while the overwhelming ansatz uses four times the trainable-gate count of the modest ansatz, which has 12.The authors note that the over-parameterized ansatz may suffer training hardness from barren plateaus.Source: Appendix G · p. 17

Hamiltonian construction

  • The hydrogen-molecule qubit Hamiltonian is obtained with the Bravyi-Kitaev transformation, and its coefficients depend on bond length.The simulations load these coefficients using OpenFermion Library.Source: Appendix G · p. 17

Hyper-parameters

  • The Adam simulations use at most 81 iterations, stop when consecutive energies differ by at most 10^-6, and initialize the learning rate at 0.4.They use β1 = 0.9, β2 = 0.99, and five repetitions; hardware-efficient ansatz depth ranges from L = 5 to L = 20.Source: Appendix G · pp. 17–18

Performance with Adam

  • With Adam, the modest ansatz performs better than the overwhelming-expressivity ansatz, and VQE performance degrades as layer count increases.At bond length 0.3 Å, the energy difference between the last two iterations is 9.4 × 10^-7 for L = 5, versus 1.9 × 10^-4, 8.9 × 10^-4, and 3.9 × 10^-2 for L = 10, 15, and 20, respectively.Source: Appendix G · p. 18, Figure G.9 · p. 18

Appendix H: Implications of Theorem 1 and Theorem 2 from the practical perspective

The section applies structural risk minimization (SRM) to VQA design, balancing training error against model complexity. It proposes three ways to control complexity using the theoretical expressivity results.

Appendix H: Implications of Theorem 1 and Theorem 2 from the practical perspective

  • SRM balances training error against model complexity, since increasing expressivity can stop improving or even degrade learning performance.The design goal is an ansatz with a modest level of expressivity.Source: Appendix H · p. 19
  • Regularizing trainable parameters, such as with λ∥θ∥2 or λ∥θ∥0, can sparsify them and control expressivity.This approach follows from the result that VQA expressivity depends on the number of trainable parameters.Source: Appendix H · p. 19
  • When the observable is trainable, its spectral norm can be included in the complexity term to tailor expressivity.The example complexity term combines λ∥θ∥2 with ∥O(γ)∥.Source: Appendix H · p. 19
  • A third approach designs the complexity term around both trainable parameters and circuit architecture, including gate-addition or deletion heuristics.This approach uses the theoretical dependence of expressivity on quantum gate types to guide structural risk minimization.Source: Appendix H · pp. 19–20
  • The authors say prior SRM approaches in Refs. [72] [73] used expressivity analysis, but their bounds did not reveal dependence on gate types.The present results are described as providing more concrete guidance, especially for architecture design.Source: Appendix H · p. 19

Appendix I: The tightness of the derived upper bound in Theorem 1

The appendix examines whether the upper bound in Theorem 1 is tight with respect to trainable parameters. Simulations show a linear relation between learning error and parameter count, with a reported fit R2 of 0.6687.

Appendix I: The tightness of the derived upper bound in Theorem 1

  • The appendix addresses a gap: to the authors' knowledge, lower bounds for VQA expressivity had not been explored.It uses numerical simulations to examine the tightness of the upper bound in Theorem 1.Source: Appendix I · p. 20
  • Because directly calculating the covering number is generally challenging, the appendix tests tightness through the QNN generalization error's relation to Ngt.The approach uses Theorem 2's connection between generalization error and QNN expressivity.Source: Appendix I · p. 20
  • R2 = 0.6687 for the fit, and learning error scales linearly with Ngt, supporting tightness of the bound with respect to parameter count.The simulations varied layer number from L = 1 to L = 15 while retaining the main-text hyperparameter settings.Source: Appendix I · pp. 20–21
Loading 2104.09961v2…