The Role of Symmetry in Quantum Query-to-Communication Simulation

• URL: http://arxiv.org/abs/2012.05233v2
• Date: Tue, 25 Apr 2023 18:10:43 GMT
• Title: The Role of Symmetry in Quantum Query-to-Communication Simulation
• Abstract summary: We show that the O(log n) overhead is required for some functions in the quantum setting, and thus the BCW simulation is tight. We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation.
• Score: 3.517404936232172
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Buhrman, Cleve and Wigderson (STOC'98) showed that for every Boolean function f : {-1,1}^n to {-1,1} and G in {AND_2, XOR_2}, the bounded-error quantum communication complexity of the composed function f o G equals O(Q(f) log n), where Q(f) denotes the bounded-error quantum query complexity of f. This is achieved by Alice running the optimal quantum query algorithm for f, using a round of O(log n) qubits of communication to implement each query. This is in contrast with the classical setting, where it is easy to show that R^{cc}(f o G) is at most 2R(f), where R^{cc} and R denote bounded-error communication and query complexity, respectively. We show that the O(log n) overhead is required for some functions in the quantum setting, and thus the BCW simulation is tight. We note here that prior to our work, the possibility of Q^{cc}(f o G) = O(Q(f)), for all f and all G in {AND_2, XOR_2}, had not been ruled out. More specifically, we show the following. - We show that the log n overhead is *not* required when f is symmetric, generalizing a result of Aaronson and Ambainis for the Set-Disjointness function (Theory of Computing'05). - In order to prove the above, we design an efficient distributed version of noisy amplitude amplification that allows us to prove the result when f is the OR function. - In view of our first result above, one may ask whether the log n overhead in the BCW simulation can be avoided even when f is transitive, which is a weaker notion of symmetry. We give a strong negative answer by showing that the log n overhead is still necessary for some transitive functions even when we allow the quantum communication protocol an error probability that can be arbitrarily close to 1/2. - We also give, among other things, a general recipe to construct functions for which the log n overhead is required in the BCW simulation in the bounded-error communication model.

Related papers

• Exact Asymptotic Rates and an Exponential Strong Converse for quantum SMP and One-Way Communication [0.0]
  We prove that the optimal worst-case communication per instance for $fn$ converges to [ Dparallel(f)=log|mathrmRow(f)|+log|mathrmCol(f)|.<n>We also prove that the same threshold governs an exponential strong converse.
  arXiv  Detail & Related papers  (2026-09-13T16:55:55Z)
• Quantum-Classical Equivalence for AND-Functions [4.0075720392218335]
  A major open problem in quantum communication complexity is whether quantum protocols can be exponentially more efficient than classical protocols.<n>We show that for every Boolean function $f$, the bounded-error quantum and classical communication complexities are deterministicly related.
  arXiv  Detail & Related papers  (2026-06-02T07:10:16Z)
• Layer-wise Lipschitz-Product Control for Deep Kolmogorov--Arnold Network Representations of Compositionally Structured Functions [51.56484100374058]
  Lipschitz product satisfies the primary domain-sensitive bound independent of the input dimension n.<n>Experiments confirm P(KAN)=1.0 for several compositionally structured functions.
  arXiv  Detail & Related papers  (2026-04-29T08:55:49Z)
• DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
  We study the computational complexity of estimating the normalized trace $2-nTr[f(A)]$ for a log-local Hamiltonian $A$ acting on $n$ qubits.<n>This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions $f(x)$.<n>We show that if $f(x)$ is a continuous function with approximate degree $(rm poly(n))$, then estimating $2-nTr[f(A)]$ up to constant additive error is
  arXiv  Detail & Related papers  (2026-04-02T01:15:12Z)
• Comparing classical and quantum conditional disclosure of secrets [0.0]
  conditional disclosure of secrets (CDS) setting is among the most basic primitives studied in cryptography.<n>We study the differences between quantum and classical CDS, with the aims of clarifying the power of quantum resources in cryptography.
  arXiv  Detail & Related papers  (2025-05-05T18:14:18Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  We study the power of unentangled quantum proofs with non-negative amplitudes, a class which we denote $textQMA+(2)$. In particular, we design global protocols for small set expansion, unique games, and PCP verification. We show that QMA(2) is equal to $textQMA+(2)$ provided the gap of the latter is a sufficiently large constant.
  arXiv  Detail & Related papers  (2024-02-29T01:35:46Z)
• Unbounded Quantum Advantage in One-Way Strong Communication Complexity of a Distributed Clique Labelling Relation [0.19090202146054183]
  We investigate the one-way zero-error classical and quantum communication complexities for a class of relations induced by a distributed clique labelling problem. We show that for the specific class of relations considered here when the players do not share any resources, there is no quantum advantage in the CCR task for any graph. We highlight some applications of this task to semi-device-independent dimension witnessing as well as to the detection of Mutually Unbiased Bases.
  arXiv  Detail & Related papers  (2023-05-17T16:58:05Z)
• 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)
• The power of qutrits for non-adaptive measurement-based quantum computing [0.0]
  We prove that quantum correlations enable the computation of all ternary functions using the generalised qutrit Greenberger-Horne-Zeilinger (GHZ) state as a resource and at most $3n-1$ qutrits. This yields a corresponding generalised GHZ type paradox for any ternary function that LHVs cannot compute.
  arXiv  Detail & Related papers  (2022-03-23T13:41:22Z)
• 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)
• Random quantum circuits transform local noise into global white noise [118.18170052022323]
  We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime. For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially. If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
  arXiv  Detail & Related papers  (2021-11-29T19:26:28Z)
• Topologically driven no-superposing theorem with a tight error bound [0.0]
  We study 'quantum addition': the superposition of two quantum states. We prove the impossibility of superposing two unknown states, no matter how many samples of each state are available. Our results exclude the superposition as an elementary gate for quantum computation.
  arXiv  Detail & Related papers  (2021-11-03T17:57:56Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)
• Trading T gates for dirty qubits in state preparation and unitary synthesis [0.0]
  We present a quantum algorithm for preparing any dimension-$N$ pure quantum state specified by a list of $N$ classical numbers. Our scheme uses $mathcalO(fracNlambda+lambdalogfracNepsilonlogfraclogNepsilon)$ to reduce the T-gate cost to $mathcalO(fracNlambda+lambdalogfracNepsilonlogfraclogNepsilon)$
  arXiv  Detail & Related papers  (2018-12-03T18:24:32Z)
• Tight Limits on Nonlocality from Nontrivial Communication Complexity; a.k.a. Reliable Computation with Asymmetric Gate Noise [19.970633213740363]
  It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. We show that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. We provide evidence that the 0.91 result is the best possible using a large class of proof strategies.
  arXiv  Detail & Related papers  (2018-09-25T22:39:03Z)

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.