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

• URL: http://arxiv.org/abs/2311.14123v1
• Date: Thu, 23 Nov 2023 17:38:16 GMT
• Title: Exponential Quantum Space Advantage for Approximating Maximum Directed Cut in the Streaming Model
• Abstract summary: We show an exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem. Our result is based on a recent $widetildetextO(sqrtn)$ space classical streaming approach.
• Score: 0.24554686192257422
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 restricted to specially-constructed problems [Le Gall, SPAA `06] or polynomial advantage [Kallaugher, FOCS `21]. We show an exponential quantum space advantage for the maximum directed cut problem. This is the first known exponential quantum space advantage for any natural streaming problem. This also constitutes the first unconditional exponential quantum resource advantage for approximating a discrete optimization problem in any setting. Our quantum streaming algorithm $0.4844$-approximates the value of the largest directed cut in a graph stream with $n$ vertices using polylog$(n)$ space, while previous work by Chou, Golovnev, and Velusamy [FOCS '20] implies that obtaining an approximation ratio better than $4/9 \approx 0.4444$ requires $\Omega(\sqrt{n})$ space for any classical streaming algorithm. Our result is based on a recent $\widetilde{\text{O}}(\sqrt{n})$ space classical streaming approach by Saxena, Singer, Sudan, and Velusamy [FOCS '23], with an additional improvement in the approximation ratio due to recent work by Singer [APPROX '23].

Related papers

• Distributed Quantum-Enhanced Optimization: A Topographical Preconditioning Approach for High-Dimensional Search [0.0]
  We show that D-QEO prevents the exponential failure rates observed in purely classical algorithms.<n>This quantum blueprint significantly reduces the number of global-term resources required to utilize.
  arXiv  Detail & Related papers  (2026-04-22T14:50:21Z)
• Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut [0.8084252698425037]
  We study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs.<n>We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size.<n>Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.
  arXiv  Detail & Related papers  (2026-02-05T18:11:18Z)
• Quartic quantum speedups for community detection [84.14713515477784]
  We develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup.<n>Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as PCA and $p$XORSAT.
  arXiv  Detail & Related papers  (2025-10-09T17:35:17Z)
• Quantum Algorithm for Online Exp-concave Optimization [30.962392035110135]
  We present quantum online quasi-Newton methods to tackle the problem. Our method approximates the Hessian by quantum estimated inexact gradient. Such regret improves the optimal classical algorithm by a factor of $T2/3$.
  arXiv  Detail & Related papers  (2024-10-25T16:58:44Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Alleviating the quantum Big-$M$ problem [0.237499051649312]
  Classically known as the "Big-$M$" problem, it affects the physical energy scale. We take a systematic, encompassing look at the quantum big-$M$ problem, revealing NP-hardness in finding the optimal $M$. We propose a practical translation algorithm, based on SDP relaxation, that outperforms previous methods in numerical benchmarks.
  arXiv  Detail & Related papers  (2023-07-19T18:00:05Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers. We find that classical solvers are capable of producing high-quality approximate solutions in linear time complexity. Other problems, such as different graphs, weighted MaxCut, maximum independent set, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
  arXiv  Detail & Related papers  (2022-06-07T20:59:19Z)
• The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut [0.07614628596146598]
  We investigate the space complexity of two graph streaming problems: Max-Cut and its quantum analogue, Quantum Max-Cut. Our work resolves the quantum and classical approximability of quantum and classical Max-Cut using $textrmo(n)$ space.
  arXiv  Detail & Related papers  (2022-06-01T03:40:56Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• A Quantum Advantage for a Natural Streaming Problem [0.07614628596146598]
  We give a one-pass quantum streaming algorithm for one of the best studied problems in classical graph counting. Almost-tight parametrized upper and lower bounds are known for streaming.
  arXiv  Detail & Related papers  (2021-06-08T18:34:22Z)
• Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
  We devise an efficient quantum differentially private (QDP) Lasso estimator to solve sparse regression tasks. Last, we exhibit that the QDP Lasso attains a near-optimal utility bound $tildeO(N-2/3)$ with privacy guarantees.
  arXiv  Detail & Related papers  (2020-07-23T10:50:42Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.