English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Although quantum algorithms realizing an exponential time speed-up over thebest known classical algorithms exist, no quantum algorithm is known performingcomputation using less space resources than classical algorithms. In thispaper, we study, for the first time explicitly, space-bounded quantumalgorithms for computational problems where the input is given not as a whole,but bit by bit. We show that there exist such problems that a quantum computercan solve using exponentially less work space than a classical computer. Moreprecisely, we introduce a very natural and simple model of a space-boundedquantum online machine and prove an exponential separation of classical andquantum online space complexity, in the bounded-error setting and for a totallanguage. The language we consider is inspired by a communication problem (theset intersection function) that Buhrman, Cleve and Wigderson used to show analmost quadratic separation of quantum and classical bounded-errorcommunication complexity. We prove that, in the framework of online spacecomplexity, the separation becomes exponential.Comment: 13 pages. v3: minor change

Exponential Separation of Quantum and Classical Online Space Complexity