Single-shot online sequence classification with unbounded quantum memory advantage

Abstract:An agent monitors a complex environment, receiving one observation at each time step and eventually deciding how to label the resulting sequence. Does the sequence indicate an anomaly, and if so, of what type? Does it signal market instability, and to what degree? This is the setting of online multi-class classification: the input arrives sequentially, the full history is never available at once, and the agent must retain any past information relevant to the eventual decision. As the environment becomes more complex, the memory needed to track this information can grow rapidly without bound. Here, we introduce families of such multi-class classification games and show that any exact classical agent requires memory that grows without bound, whereas exact quantum agents can solve all tasks in the family with bounded memory. This separation is sharp: any classical agent using less than the required memory, under suitable input distributions, performs arbitrarily close to random guessing. Moreover, our quantum constructions are provably memory minimal, allowing us to derive the exact classical and quantum memory complexities to perform such tasks. In doing so, we establish an unbounded separation between classical and quantum memory cost for online multi-class classification.

arXiv:2608.23669 [quant-ph]

(or arXiv:2608.23669v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2608.23669 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.