Quantum-Enhanced Inference of Conditional Future Probabilities with Reduced Memory Cost

The gist: This work offers quantum-algorithmic means to reduce systematic bias while maintaining a quadratic speed-up for estimating conditional future probabilities in stochastic systems with reduced memory cost.

Problem Statement

The objective is to estimate the likelihood of a target future event up to some time horizon L, formalised as the subset of futures that satisfy some binary property f. This involves computing p:= P[f(x0:L) = 1 ←−x]:= Pf←−x. Classical estimation through statistical sampling is constrained by the central limit theorem, requiring O(1/ϵ 2) independent samples to achieve an additive error epsilon. The primary resource concerns are the number of times N that needs to be simulated and the number of distinct memory states D tracked by the model.

Classical Baseline

In classical settings, a standard approach involves statistical sampling using a predictive model M, where each past ←−x is encoded into a memory state si ∈ S. The performance is benchmarked by the root mean squared error (RMSE), defined as ϵ = p E[(p − pb) 2]. The first concern is the number of times N that needs to simulate the process, which scales as 1/ϵ squared. The second concern is the number of distinct memory states D = S tracked by the model, which can grow rapidly in modern sequence-modelling settings.

Quantum Amplitude Estimation (QAE)

QAE promises a quadratic reduction in the number of simulations needed, reducing that cost to O(1/ϵ). QAE relies on a quantum circuit A that maps 0⟩ to its quantum sample ϕZ⟩ = P z √p z z⟩. The Grover operator Q = -AS0A†Sχ, where S0 = I−2 0⟩ ⟨0 is a reflection operator about the all-zero state, and Sχ is the oracle that marks the target subspace. Standard QAE uses this Grover operator within a phase estimation subroutine, scaling the number of times A scales only as 1/ϵ.

Model Reduction and Distortion

To address the cost of generating each sample (executing A), model reduction is paramount, motivated by identifying the minimal memory dimension D required to sample P(x0:L ←−x) faithfully. This minimal memory dimension is bounded by the topological state complexity Dc = log2(Dc), which lowerbounds the memory dimension of M. When forced to use a target memory constraint D < D˜c, a biased model is used, and any A obtained inherits similar bias. This leads to distortion where the approximate model estimates ˆp by sampling from some induced distribution P˜(X0:L ←−x) that approximates P. The resulting errors comprise (1) random contributions ϵrand, and (2) systematic bias ϵb, which does not diminish with N, and as N → ∞, the total error satisfies ϵ → P˜f←−x − Pf←−x, which does not approach 0.

Approach

The approach exploits the fact that quantum models with a fixed memory dimension D˜ are more expressive, allowing for an efficient implementation of A whose bias is significantly lower than the baseline approach. The process involves defining an associated quantum model Mq that associates each sj with a corresponding quantum memory state sj ⟩. The unitary Us couples its memory to the ancilla, satisfying Us si⟩ 0⟩ = X x Σ j X x q T x ij sj ⟩ x⟩.

Complexity

The CNOT gate complexity for implementing A is O(L · D squared · X 2). If the quantum model is direct map from classical models using orthogonal encoding, the complexity is O(L · D squared c · X 2). If the quantum model is created using a non-orthogonal encoding, then D = Dq ≤ Dc, resulting in O(L · D squared q · X 2). If the quantum model is further compressed to D < D˜q, the complexity becomes O(L · D˜ squared · X 2).

Illustrative Example

In an illustrative example of a particle on a ring, constraining memory dimension to 4-state models (D˜ = 4) resulted in the quantum model exhibiting significantly less bias compared to classical counterparts. The quantum model achieved an average RMSE below the classical bound at around N ∼ 2 × 10 4 samples.

Discussion

The resulting quantum-enhanced future inference algorithm exhibits (i) the typical speed-up of QAE from a quadratic improvement in how many times we need to simulate the process and (ii) further improved memory-distortion trade-offs that enable reduced errors from finite-memory constraints.

Future Directions

One promising direction is to incorporate classical importance sampling techniques, where quantum processing turns out particularly effective in reducing the complexity of such variants, where resulting models can have unbounded memory advantage. Another direction involves further circuit optimisation, noting that the gate complexities quoted for our quantum models are presently worst-case scenarios. Integration with existing transformer and RNN models has exciting prospects, as quantum models have shown provably unbounded memory advantage in such settings.

Numerical Results

Numerical simulations for the cyclic random walk showed that the truncated model achieved a mean absolute error of 0.0679 compared to 0.126 for the untruncated model when memory dimension was constrained to 4. This reduction in estimation error of more than 50% persisted across the full output alphabet.

Finer Discretization and the Continuum Limit

The analysis showed that finer discretization does not force the distortion introduced by quantum memory reduction to increase, as RF = P(k)⟩, P˜(k)⟩ ≤ O C(k) q / n! = O C(k) q log2 D˜! This suggests that the quantum advantage observed here is not specific to the particular discretization precision used in our original proof-of-principle example.

Noisy Process Performance

On noisy processors, dimensional reduction provides an additional practical advantage because decreasing the size of the unitary required to simulate the process may also substantially reduce the gate count and gate error accumulation. The truncated model yielded a mean absolute error of 0.0679 compared to 0.126 for the untruncated model when memory dimension was constrained to 4, even with a CNOT depolarizing error rate of 7.9×10−4.

Conclusion on Advantage

The quantum advantage observed here is not specific to the particular discretization precision used in our original proof-of-principle example, as the reduced quantum models outperform classical baseline models subject to the same memory constraints. This provides strong evidence that the quantum advantage observed here is not specific to the particular discretization precision used in our original proof-of-principle example.

1. Improved conditional probability estimation for complex stochastic systems: The algorithm estimates the likelihood of a target future event up to some time horizon L by leveraging quantum amplitude estimation (QAE) which promises a quadratic reprieve, reducing simulation cost from O(1/ϵ 2) to O(1/ϵ).

2. Enhanced memory-distortion trade-off management: By exploiting the fact that quantum models with a fixed memory dimension D˜ are more expressive, the system can be designed to achieve significantly lower bias than baseline approaches, specifically when "D < D˜ c allows for a means to design quantum models whose conditional future statistics more closely approximate P."

3. Accelerated rare-event classification: The system achieves a reduction in estimation error that is superior to classical bounds, demonstrated by the ability of the quantum model to achieve an RMSE that dips below this bound at around N ∼ 2 × 104 samples for rare events, providing a speedup where quantum models can achieve RMSE below classical limits using only around 3000 samples.

4. Noise-resilient inference on NISQ devices: The dimensional reduction method offers a practical advantage on noisy hardware, as the reduction in hardware-induced error can outweigh the truncation bias, leading to a reduction in estimation error of more than 50% compared to untruncated models when simulating processes like the cyclic random walk.

5. Adaptive simulation scheduling: The implementation utilizes schedules like Linear Increment Schedule (LIS) and Exponential Increment Schedule (EIS) within the Maximum Likelihood Amplitude Estimation (MLAE) framework, allowing for a quadratic speed-up due to reduced sampling complexity while optimizing how measurements are distributed across the number of Grover iterations.

Many potential future events have devastating consequences, from the onset of earthquakes to financial black swan events. Accurate predictions of their probability of occurrence are vital. Yet as the stochastic systems underlying such events become increasingly complex, these probabilities can depend on ever-growing amounts of past data, which require ever more memory to track. The accuracy of our estimates is ultimately limited by both computational and memory constraints; the former to reduce sampling error, the latter to avoid sampling bias. Traditional quantum algorithms -- such as amplitude estimation -- address only the former, and become untenable especially in near-future quantum devices where quantum memory is a premium. Here, we offer quantum-algorithmic means to reduce systematic bias while maintaining a quadratic speed-up. Our results thus advance the timeline for the practical deployment of quantum technologies, and illustrate their additional benefits when simulating processes of growing complexity.