Quantum advantage in zero-error function computation with side information

• URL: http://arxiv.org/abs/2402.01549v3
• Date: Tue, 14 Jan 2025 23:45:09 GMT
• Title: Quantum advantage in zero-error function computation with side information
• Authors: Ruoyu Meng, Aditya Ramamoorthy,
• Abstract summary: We consider the problem of zero-error function computation with side information. Alice and Bob have correlated sources $X,Y$ with joint p.m.f. $p_XY(cdot, cdot)$. We study the behavior of the quantum advantage in the single-instance case and the case for several classes of confusion graphs.
• Score: 10.0060346233449
• License:
• Abstract: We consider the problem of zero-error function computation with side information. Alice and Bob have correlated sources $X,Y$ with joint p.m.f. $p_{XY}(\cdot, \cdot)$. Bob wants to calculate $f(X,Y)$ with zero error. Alice communicates $m$-length blocks $(m \geq 1)$ with Bob over error-free channels: classical or quantum. In the classical setting, the minimum communication rate depends on the asymptotic growth of the chromatic number of an appropriately defined $m$-instance ``confusion graph'' $G^{(m)}$. In the quantum setting, it depends on the asymptotic growth of the orthogonal rank of the complement of $G^{(m)}$. The behavior of the quantum advantage (ratio of classical and quantum rates) depends critically on $G^{(m)}$ which is shown to be sandwiched between $G^{\boxtimes m}$ ($m$-times strong product) and $G^{\lor m}$ ($m$-times OR product) respectively. Our work presents necessary and sufficient conditions on the function $f(\cdot, \cdot)$ and joint p.m.f. $p_{XY}(\cdot,\cdot)$ such that $G^{(m)}$ equals either $G^{\boxtimes m}$ or $G^{\lor m}$. We study the behavior of the quantum advantage in the single-instance case and the asymptotic (in $m$) case for several classes of confusion graphs and demonstrate, e.g., that there exist problems where there is a quantum advantage in the single-instance rate but no quantum advantage in the asymptotic rate.

Related papers

• The classical limit of Quantum Max-Cut [0.18416014644193066]
  We show that the limit of large quantum spin $S$ should be understood as a semiclassical limit. We present two families of classical approximation algorithms for $mathrmQMaxCut_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states.
  arXiv  Detail & Related papers  (2024-01-23T18:53:34Z)
• 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)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  We give a quantum approximation scheme for the classical $k$-means clustering problem in the QRAM model. Our quantum algorithm runs in time $tildeO left( 2tildeO(frackvarepsilon) eta2 dright)$. Unlike previous works on unsupervised learning, our quantum algorithm does not require quantum linear algebra subroutines.
  arXiv  Detail & Related papers  (2023-08-16T06:46:37Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum Security of iMHFs [6.305950347749109]
  We introduce a new parallel reversible pebbling game which captures additional restrictions imposed by the No-Deletion Theorem in Quantum Computing. We apply our new reversible pebbling game to analyze the reversible space-time complexity of several important graphs.
  arXiv  Detail & Related papers  (2021-10-08T15:24:31Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• $k$-Forrelation Optimally Separates Quantum and Classical Query Complexity [3.4984289152418753]
  We show that any partial function on $N$ bits can be computed with an advantage $delta$ over a random guess by making $q$ quantum queries. We also conjectured the $k$-Forrelation problem -- a partial function that can be computed with $q = lceil k/2 rceil$ quantum queries.
  arXiv  Detail & Related papers  (2020-08-16T21:26:46Z)
• Lower Bounds for XOR of Forrelations [7.510385608531827]
  We study the XOR of $k$ independent copies of the Forrelation function. We also show that any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess.
  arXiv  Detail & Related papers  (2020-07-07T17:05:09Z)
• Quantum Coupon Collector [62.58209964224025]
  We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements. We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
  arXiv  Detail & Related papers  (2020-02-18T16:14:55Z)

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.