|
| | | | |
| | | |
| Stat |
Members: 3657
Articles: 2'599'751
Articles rated: 2609
14 October 2024 |
|
| | | | |
|
Article overview
| |
|
|
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut | | John Kallaugher
; Ojas Parekh
; | | Date: |
1 Jun 2022 | | Abstract: | We investigate the space complexity of two graph streaming problems: Max-Cut
and its quantum analogue, Quantum Max-Cut. Previous work by Kapralov and
Krachun [STOC ’19] resolved the classical complexity of the emph{classical}
problem, showing that any $(2 - varepsilon)$-approximation requires
$Omega(n)$ space (a $2$-approximation is trivial with $ extrm{O}(log n)$
space). We generalize both of these qualifiers, demonstrating $Omega(n)$ space
lower bounds for $(2 - varepsilon)$-approximating Max-Cut and Quantum Max-Cut,
even if the algorithm is allowed to maintain a quantum state. As the trivial
approximation algorithm for Quantum Max-Cut only gives a $4$-approximation, we
show tightness with an algorithm that returns a $(2 +
varepsilon)$-approximation to the Quantum Max-Cut value of a graph in
$ extrm{O}(log n)$ space. Our work resolves the quantum and classical
approximability of quantum and classical Max-Cut using $ extrm{o}(n)$ space.
We prove our lower bounds through the techniques of Boolean Fourier analysis.
We give the first application of these methods to sequential one-way quantum
communication, in which each player receives a quantum message from the
previous player, and can then perform arbitrary quantum operations on it before
sending it to the next. To this end, we show how Fourier-analytic techniques
may be used to understand the application of a quantum channel. | | Source: | arXiv, 2206.00213 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER