Erratum: Expressive power of parametrized quantum circuits [Phys. Rev. Research 2, 033125 (2020)]

Yuxuan Du, Min-Hsiu Hsieh, Tongliang Liu, Dacheng TaoPhysical 2022 · DOI · OpenAlex

Abstract

This mini-paper summarizes the formal correction to the 2020 study "Expressive power of parametrized quantum circuits." The erratum addresses a critical oversight in the original Theorem 2 concerning the simulation of classical Boltzmann machines by multi-layer parametrized quantum circuits (MPQCs). By incorporating the computational complexity of partition functions, the authors refine the conditions under which quantum circuits demonstrate superior expressive power, ensuring a mathematically rigorous comparison between classical and quantum generative models.

Introduction

In the original publication [Phys. Rev. Research 2, 033125 (2020)], the authors established a framework to quantify the "expressive power" of multi-layer parametrized quantum circuits (MPQCs). A central claim of the work was that MPQCs could efficiently simulate probability distributions generated by Restricted Boltzmann Machines (RBMs) and Deep Boltzmann Machines (DBMs). However, a subsequent review identified a nuance regarding the NP-hardness of calculating partition functions in energy-based models. This erratum provides the necessary theoretical refinements to maintain the validity of the paper’s core thesis.

The Problem: The Partition Function Bottleneck

Energy-based models, such as RBMs, define the probability of a specific state based on its energy relative to a global partition function ($Z$). The partition function is the sum of the Boltzmann factors over all possible configurations of the system. In general, calculating $Z$ is a #P-complete problem, making it computationally intractable for large-scale classical systems.

In the original Theorem 2, the authors claimed that MPQCs could simulate RBM distributions using only a polynomial number of quantum gates. The oversight lay in the definition of "efficiency." If the classical distribution itself cannot be prepared or sampled from efficiently due to the hardness of $Z$, then a quantum simulation of that distribution does not necessarily prove a practical advantage unless the comparison is restricted to the "efficiently computable" regime of classical models.

Revised Theorem 2 and Methodology

To resolve this, the authors re-evaluated the complexity classes involved in preparing these distributions. They introduced a more rigorous comparison between:

  • Classical Complexity ($C_A$): The time required for a classical model to prepare or sample from a probability distribution.
  • Quantum Complexity ($C_B$): The gate count or runtime for an MPQC to prepare the equivalent distribution.

The Logarithmic Constraint

The revised proof acknowledges that for a classical RBM to produce a distribution in polynomial time ($O[poly(N)]$), the number of neurons cannot scale linearly with the system size $N$. Instead, the total number of neurons must be constrained to a logarithmic scale ($O\{\ln[poly(N)]\}$).

Leveraging recent advancements in quantum complexity theory (notably Hsieh et al., 2021), the authors demonstrate that these specific, classically efficient distributions can indeed be mapped onto quantum circuits using polynomial resources. This leads to the Revised Theorem 2:

Any probability distribution produced by short-range RBMs, long-range RBMs, or deep Boltzmann machines (DBMs) in $O[poly(N)]$ runtime complexity can be generated by some MPQCs in $O[poly(N)]$ runtime complexity.

Discussion and Key Insights

The primary insight of this erratum is the "Fair Comparison" principle. To claim that a quantum model is more expressive than a classical one, the comparison must be grounded in the subset of classical models that are actually usable in practice. By narrowing the scope to distributions where $Z$ is tractable, the authors bridge the gap between abstract mathematical expressivity and real-world computational complexity.

Crucially, this correction does not invalidate the original paper's primary conclusion. It maintains the hierarchy of expressiveness: if a classical model can prepare a distribution in $C_A$ time, a quantum circuit can achieve the same in $C_B$ time, where $C_A \geq C_B$. The erratum simply ensures that the baseline ($C_A$) is well-defined within the bounds of polynomial efficiency.

Conclusion

The refinement of Theorem 2 reinforces the theoretical foundation for using MPQCs in generative modeling. While the NP-hardness of the partition function remains a fundamental challenge in classical machine learning, this work clarifies that quantum circuits possess the necessary expressive power to encompass all classically efficient energy-based models. Future research will continue to seek specific distribution classes where quantum circuits provide a provable exponential speedup over classical approximations.

Summary updated

Abstract

Received 30 May 2022DOI:https://doi.org/10.1103/PhysRevResearch.4.029003Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.Published by the American Physical SocietyPhysics Subject Headings (PhySH)Research AreasMachine learningQuantum Information
BibTeX
@inproceedings{du2022erratum,
  author = {Yuxuan Du and Min-Hsiu Hsieh and Tongliang Liu and Dacheng Tao},
  title = {{Erratum: Expressive power of parametrized quantum circuits [Phys. Rev. Research 2, 033125 (2020)]}},
  booktitle = {Physical},
  year = {2022},
  doi = {10.1103/physrevresearch.4.029003},
}

Loading related content...

Figure