Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with quantum vs classical:
TR17-176 | 15th November 2017
Kamil Khadiev, Aliya Khadiev, Alexander Knop

Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies

In this paper, we study quantum OBDD model, it is a restricted version of read-once quantum branching programs, with respect to "width" complexity. It is known that the maximal gap between deterministic and quantum complexities is exponential. But there are few examples of functions with such a gap. We present ... more >>>

TR23-189 | 28th November 2023
John Kallaugher, Ojas Parekh, Nadezhda Voronova

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

While the search for quantum advantage typically focuses on speedups in execution time, quantum algorithms also offer the potential for advantage in space complexity. Previous work has shown such advantages for data stream problems, in which elements arrive and must be processed sequentially without random access, but these have been ... more >>>

ISSN 1433-8092 | Imprint