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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

While the search for quantum advantage typically focuses on speedups inexecution time, quantum algorithms also offer the potential for advantage inspace complexity. Previous work has shown such advantages for data streamproblems, in which elements arrive and must be processed sequentially withoutrandom access, but these have been restricted to specially-constructed problems[Le Gall, SPAA `06] or polynomial advantage [Kallaugher, FOCS `21]. We show anexponential quantum space advantage for the maximum directed cut problem. Thisis the first known exponential quantum space advantage for any naturalstreaming problem. This also constitutes the first unconditional exponentialquantum resource advantage for approximating a discrete optimization problem inany setting.  Our quantum streaming algorithm $0.4844$-approximates the value of thelargest directed cut in a graph stream with $n$ vertices using polylog$(n)$space, while previous work by Chou, Golovnev, and Velusamy [FOCS '20] impliesthat obtaining an approximation ratio better than $4/9 \approx 0.4444$ requires$\Omega(\sqrt{n})$ space for any classical streaming algorithm. Our result isbased on a recent $\widetilde{\text{O}}(\sqrt{n})$ space classical streamingapproach by Saxena, Singer, Sudan, and Velusamy [FOCS '23], with an additionalimprovement in the approximation ratio due to recent work by Singer [APPROX'23].

Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model