⚛️ quantum physics

Comment on "Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency": Polynomial Evaluation of the Triplet-Block Readout

This paper refutes the claim of exponential classical cost for the triplet-block two-body readout in scalable quantum machine learning by demonstrating that diagonal two-particle reduced density matrices enable a deterministic $O(n^4)$ algorithm for computing complete correlator vectors, thereby invalidating the specific algorithm-relative exponential-cost conclusion while leaving other trainability and hardness results unaffected.

Original authors: Erfan Amidi

Published 2026-08-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Erfan Amidi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quest to build machines that can learn from data using the strange laws of quantum physics, scientists are constantly trying to figure out where the real power lies and where the limits are. Imagine a computer that doesn't just calculate numbers but explores many possibilities at once, using particles like electrons that can exist in multiple states simultaneously. This is the promise of quantum machine learning. However, for these systems to be useful, researchers must be able to train them, which involves adjusting knobs and dials to improve their performance. A major hurdle in this field is knowing whether a computer running on ordinary silicon chips can predict what a quantum machine will do, or if the quantum machine is so complex that only the quantum machine itself can understand its own output. If a classical computer can easily predict the result, the quantum system might not offer a unique advantage. This question of "trainability" and efficiency is central to deciding whether these futuristic devices will ever move from theory to reality.

A recent note by researcher Erfan Amidi addresses a specific claim about how difficult it is to calculate the output of a particular type of quantum learning model. In a previous study, scientists had suggested that for a specific setup involving groups of three particles, calculating the relationships between pairs of particles would require a massive amount of time for any classical computer. They estimated that the time needed would grow exponentially as the system got larger, essentially making it impossible to simulate on a normal computer. This conclusion was based on a method that treated the entire quantum state as a complex sum of many simpler parts, a process that quickly becomes unmanageable as the number of parts increases. The previous researchers argued that because the input state was complex, the only way to get the answer was to perform this expensive calculation, which would take an impractical amount of time.

Amidi's work shows that this conclusion was based on an unnecessary complication. The researcher demonstrates that for the specific task of measuring how pairs of particles are correlated, there is a much simpler path. Instead of trying to track the entire complex quantum state, one can focus only on the information that matters for the specific measurement. The input state in question is built from blocks of particles, and while the full description of these blocks is intricate, the specific information needed to predict the pair-wise relationships is actually very simple and can be written down directly. It turns out that the complex parts of the quantum state do not interfere with each other in a way that matters for this specific measurement. Because of this, the calculation does not require the exponential explosion of time that was previously feared.

The new analysis provides a clear, step-by-step method to calculate these relationships using a standard computer. The method involves taking a simple list of probabilities that describes the starting state and applying a mathematical transformation that represents how the particles move and interact. This transformation can be calculated very quickly, even as the number of particles grows. The result is a complete list of all the pair-wise relationships in a time that grows only as the fourth power of the number of particles. For a system with a thousand particles, this is a task a modern computer can handle easily, whereas the previous estimate suggested it would take longer than the age of the universe. This finding proves that the specific quantum learning model in question is not as hard to simulate as once thought, at least for the task of measuring these specific correlations.

This discovery does not mean that quantum computers have lost all their mystery or potential. The researcher is careful to point out that while these specific measurements are easy to predict, other tasks involving the full complexity of the system, such as generating random outcomes or measuring more complex relationships involving many particles at once, remain difficult for classical computers. The difficulty of training the quantum system, the risk of the system getting stuck in a state where it cannot learn, and the challenge of sampling random results are all still valid concerns that were not changed by this new finding. The new work simply clarifies that for the specific job of reading out the two-particle relationships in this particular setup, the classical cost is low and the calculation is straightforward.

The significance of this work lies in its ability to correct the map of what is possible and what is not in the landscape of quantum machine learning. By showing that a previously assumed barrier was actually an illusion created by using a more complicated tool than necessary, the researcher has helped refine our understanding of where the true advantages of quantum systems lie. It suggests that for certain types of data and measurements, classical computers can keep pace with quantum ones, which is a crucial piece of information for engineers designing these future technologies. The work confirms that while the quantum world is vast and complex, there are specific windows into it that remain clear and accessible, allowing us to build better models of how these systems learn and behave without needing to solve the impossible.

Technical Summary: Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency – Polynomial Evaluation of the Triplet-Block Readout

Problem Statement
This work addresses a specific claim regarding the classical computational cost of evaluating the "supervised two-body readout" in a quantum machine learning architecture described in Reference [1]. Reference [1] analyzes a system of $n$ fermionic modes initialized in a "triplet-block" state, defined as $|\Psi_{\text{in}}\rangle = |\Psi_6\rangle^{\otimes m} \otimes |0\rangle^{\otimes (n-6m)}$ , where $|\Psi_6\rangle = (|111000\rangle + |000111\rangle)/\sqrt{2}$ . The system undergoes passive fermionic linear optics (FLO) operations, and the readout consists of the vector of two-body number correlators $q_{ij} = \langle n_i n_j \rangle$ .

Reference [1] argued that because the input state has a "form-rank" of 3 (preventing the use of mixed-Pfaffian compression available for rank-2 states), the only viable classical simulation route was a Gaussian-state expansion. This expansion involves $\chi = 2^{k/3}$ terms, leading to a classical evaluation cost of $O(\chi^2 \text{poly}(n)) = O(2^{2k/3} \text{poly}(n))$ . Consequently, Reference [1] concluded that evaluating this readout vector is classically intractable (exponential in $k$ ), rendering the associated supervised learning features classically inaccessible.

Methodology
The author challenges the necessity of the full Gaussian expansion by focusing on the specific structure of the observable and the input state. The methodology proceeds as follows:

Fixed-Body Closure under FLO: The paper establishes that passive FLO unitaries, $U_W$ , act on the $r$ -particle sector of a fermionic state via a linear transformation of the $r$ -particle reduced density matrix (RDM), $\Gamma^{(r)}$ . Specifically, if $\rho$ is the input state, the output state $\rho_{\text{out}} = U_W \rho U_W^\dagger$ satisfies:
$\Gamma^{(r)}_{\rho_{\text{out}}} = R_r(W) \Gamma^{(r)}_{\rho} R_r(W)^\dagger$
where $R_r(W) = \bigwedge^r W$ is the $r$ -th exterior power of the single-particle unitary $W$ . The matrix elements of $R_r(W)$ are determinants of $r \times r$ submatrices of $W$ .
Diagonal Input Structure: The author demonstrates that for the specific triplet-block input, the two-particle reduced density matrix ( $r=2$ ) is explicitly diagonal. This is because the two branches of the triplet state ( $|111000\rangle$ and $|000111\rangle$ ) differ by three occupied modes; thus, any two-body operator (which can change at most two modes) has zero coherence between these branches. The diagonal entries of $\Gamma^{(2)}_{\text{in}}$ are explicitly computable constants ( $1/2$ , $1/4$ , or $0$) depending on the mode indices.
Deterministic Propagation: By combining the diagonal nature of the input $\Gamma^{(2)}_{\text{in}}$ with the linear propagation rule, the author derives a closed-form expression for the output correlators. The expectation value for any pair $(i, j)$ is computed as a sum over the diagonal weights of the input RDM weighted by the squared moduli of the determinants of the corresponding submatrices of $W$ .

Key Contributions and Results

Polynomial-Time Algorithm: The paper presents a deterministic classical algorithm to compute the complete two-body correlator vector $q(x, \theta)$ in $O(n^4)$ time. This complexity is independent of the number of blocks $m$ (and thus the parameter $k$ ) and the form-rank of the full input state.
Generalization to Fixed- $r$ Observables: The work generalizes this result to any number-conserving $r$ -body expectation value. If the input $r$ -particle RDM is classically available, the output expectation is computable in polynomial time $O(n^{2r})$ (specifically $O(r^3 \binom{n}{r}^2)$ ). If the input RDM is diagonal, the cost is $O(n^{2r})$ .
Refutation of Exponential Cost: The author demonstrates that the $O(2^{2k/3})$ bound cited in Reference [1] is an artifact of using a suboptimal simulation method (full Gaussian expansion) rather than a fundamental complexity-theoretic lower bound. The specific structure of the triplet-block readout allows for efficient classical simulation.

Significance and Claims
The paper asserts that its findings invalidate the claim in Reference [1] that the supervised two-body readout for triplet-block inputs requires exponential classical time. Specifically:

The "classically inaccessible" nature of the feature vector is removed; the vector and its gradients can be computed efficiently.
The conclusion that the "expectation-value hardness" implies a barrier to classical simulation for these specific models is overturned.
The results do not affect other conclusions in Reference [1], such as those regarding gradient variance, barren plateaus, parameter-shift rules, or sampling hardness. The sampling hardness remains because full output probabilities depend on correlations of body order growing with the system size, which are not captured by fixed- $r$ RDMs.

Note on Context
The author notes that Version 2 of Reference [1] (posted August 20, 2026) subsequently removed the triplet encoding and the associated expectation-value hardness claims, acknowledging the fixed-body simulability result in a general form. This paper serves as the technical justification for that revision.

Technical Summary: Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency – Polynomial Evaluation of the Triplet-Block Readout

More like this