A new algorithm enables polynomially scalable computations for certain quantum mechanical properties. Previously, computing number-conserving fixed-r-body expectations was thought to require exponential computational cost, but it is now possible when access to the input r-particle reduced density matrix is granted. This advancement allows complete correlator vectors to be computed in O(n 4 ) time, irrespective of system size or other parameters, representing a substantial improvement over existing methods.

Calculations of specific quantum properties are now more efficient than previously believed and challenge assumptions about unavoidable increases in computational demands when measuring quantum systems. The calculations can be completed within a predictable timeframe; specifically, an amount of time that grows at a rate proportional to the fourth power of system size (O(n 4 )). Calculations focused on ‘number-conserving fixed-r-body expectations’, relating to how many particles occupy specific states within a system, require examining the ‘r-particle reduced density matrix’.

This simplified snapshot captures only probabilities of finding particles in particular states, similar to focusing on overall colour distribution in a painting rather than every individual brushstroke. By using characteristics of this input data and utilising passive fermionic linear optics, a set of tools used to manipulate electrons without direct observation, akin to prisms and lenses with light, we achieve calculations in O(n 4 ) time; key independence from system size is maintained.

Efficient computation of many-body correlation functions via optimised algorithmic scaling

Complete correlator vectors can now be computed in O(n⁴) time; this represents an improvement over previous methods requiring O(2²/³poly(n)) operations, where ‘k’ defines system complexity and ‘n’ denotes system size. Earlier algorithms scaled exponentially with the parameter ‘k, hindering analysis of complex quantum states, but this breakthrough crosses a threshold previously considered impossible for larger systems. We achieve polynomial scalability when accessing only the input r-particle reduced density matrix, enabling calculations formerly deemed intractable without full Gaussian-state expansion.

The advancement relies on utilising properties within triplet-block inputs possessing readily computable diagonal two-particle data, simplifying computations through passive fermionic linear optics, tools manipulating electrons without direct observation. This simplified representation alongside these techniques improves efficiency; specifically, any number-conserving calculation involving only ‘r’ particles can be performed in polynomial time if the initial r-particle reduced density matrix is known.

We achieve all diagonal correlations in O(n²) time with a diagonal input matrix and this applies even to complex states lacking Gaussian decomposition, invalidating previous claims of exponential cost for certain readouts while leaving other areas like gradient variance unaffected.

Triplet-block decomposition and scalable quantum simulation using passive fermionics

Passive fermionic linear optics proved central to achieving this computational advance, these tools manipulate electrons without directly observing their individual characteristics, similar to analysing light with prisms and lenses without destroying it. The team exploited that triplet-block inputs possess a readily computable diagonal two-particle reduced density matrix, offering a simplified snapshot capturing probabilities of finding particles in particular states.

We propagated this data through specifically designed layers utilising the approach bypassing previously anticipated exponential scaling issues; consequently, we demonstrated classical computation of the triplet-block two-body readout in O(n⁴) time. Gaussian-state expansion methods were not necessary for fixed-body observables, bypassing an anticipated cost scaling exponentially with ‘k, a parameter related to quantum state complexity.

Reduced density matrix access limits algorithmic gains in quantum simulation

The refined calculations offer a pathway towards streamlining simulations of complex quantum systems; however, accessing the ‘r-particle reduced density matrix’, a simplified representation of particle probabilities potentially elusive in certain physical scenarios, is vital. While this new algorithm demonstrably reduces computational demands for specific tasks like calculating how many particles occupy particular states, it doesn’t address broader challenges plaguing quantum machine learning such as barren plateaus where gradients vanish during training or difficulties associated with obtaining meaningful samples from these models. This analysis establishes a computationally efficient method for calculating specific properties within complex quantum systems and challenges previous assumptions about unavoidable increases in processing demands when measuring those states. By focusing on ‘number-conserving fixed-r-body expectations’, describing particle distribution and utilising the simplified representation of probabilities offered by the r-particle reduced density matrix, calculations scaling at a predictable rate proportional to system size were achieved. This advancement demonstrates that determining certain quantum characteristics is possible with polynomial rather than exponential computational resources given access to initial data, opening avenues for streamlining simulations.

The researchers found a way to calculate complete correlator vectors for up to two particles in O(n⁴) time, demonstrating classical computation without needing complex Gaussian-state expansion methods. This means calculating these specific properties within quantum systems requires processing power that increases predictably alongside system size, instead of exponentially.

The work highlights that accessing classically available ‘r-particle reduced density matrices’ limits algorithmic gains in quantum simulation; the authors showed this approach applies generally to number-conserving fixed-r-body expectations with diagonal correlation matrices computable in O(n²) time. These findings invalidate previous conclusions about exponential costs associated with supervised two-body readout.

👉 More information
🗞 Comment on “Scalable Quantum Machine Learning: Trainability, Expressivity and Efficiency”: Polynomial Evaluation of the Triplet-Block Readout
✍️ Erfan Amidi
🧠 ArXiv: https://arxiv.org/abs/2608.20435

More like this