A Hierarchy for Replica Quantum Advantage

• URL: http://arxiv.org/abs/2111.05874v1
• Date: Wed, 10 Nov 2021 19:00:06 GMT
• Title: A Hierarchy for Replica Quantum Advantage
• Abstract summary: Given the ability to make entangled measurements on at most $k$ replicas of an $n$-qubit state $rho$ simultaneously, there is a property of $rho$ which requires at least order $2n / k2$ measurements to learn. We introduce a powerful proof technique to establish our results, and also use this to provide new bounds for testing the mixedness of a quantum state.
• Score: 17.763817187554096
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove that given the ability to make entangled measurements on at most $k$ replicas of an $n$-qubit state $\rho$ simultaneously, there is a property of $\rho$ which requires at least order $2^n / k^2$ measurements to learn. However, the same property only requires one measurement to learn if we can make an entangled measurement over a number of replicas polynomial in $k, n$. Because the above holds for each positive integer $k$, we obtain a hierarchy of tasks necessitating progressively more replicas to be performed efficiently. We introduce a powerful proof technique to establish our results, and also use this to provide new bounds for testing the mixedness of a quantum state.

Related papers

• Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms [42.57939149964391]
  We study quantum multi-armed bandits (QMAB) and quantum linear bandits (QLB)<n>We prove the first minimax lower bounds of $(Klog(T/K))$ for QMAB and $(dlog(T/d))$ for finite-action QLB.
  arXiv  Detail & Related papers  (2026-08-14T14:04:21Z)
• Random Projections for Multi-Copy Quantum Algorithms [3.995502708329505]
  Estimating nonlinear properties of quantum states is a central task in quantum information science.<n>Standard protocols based on swap tests require coherent operations on the full Hilbert space.<n>We introduce a framework for multi-copy measurements based on random projections onto lower-dimensional subspaces.
  arXiv  Detail & Related papers  (2026-06-18T13:49:14Z)
• The Exact Replica Threshold for Nonlinear Moments of Quantum States [1.599072005190786]
  We prove that the exact replica threshold for fixed-order pure moments is $lceil t/2rceil$.<n>For fixed-order pure moments, one additional coherent replica is not merely useful but marks the exact threshold between-sample estimation and a-growing regime.
  arXiv  Detail & Related papers  (2026-04-24T14:56:59Z)
• Optimal Quantum State Testing Even with Limited Entanglement [13.84229509611525]
  We consider the fundamental task of quantum state certification: given copies of an unknown quantum state $$, test whether it matches some target state $$ or is $$-far from it.<n>Our main result is a smooth copy complexity upper bound for state certification as a function of $t$, which achieves a near-optimal rate at $t = d2$.<n>We extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at $t = d2$ as well.
  arXiv  Detail & Related papers  (2026-04-08T18:01:51Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Instance-Optimal Quantum State Certification with Entangled Measurements [1.8416014644193066]
  We prove nearly instance-optimal bounds for quantum state certification when the tester can perform fully entangled measurements.<n>We prove our lower bounds using a novel quantum analogue of the Ingster-Suslina method, which is likely to be of independent interest.
  arXiv  Detail & Related papers  (2025-07-08T14:15:46Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We show that the rank of a function $f$ corresponds to the minimum number of Chain of Thought steps required by a single-layer transformer decoder. We also analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• Coherence in Property Testing: Quantum-Classical Collapses and Separations [42.44394412033434]
  We show that no tester can distinguish subset states of size $2n/8$ from $2n/4$ with probability better than $2-Theta(n)$.<n>We also show connections to disentangler and quantum-to-quantum transformation lower bounds.
  arXiv  Detail & Related papers  (2024-11-06T19:52:15Z)
• Nearly tight bounds for testing tree tensor network states [0.0]
  Tree tensor network states (TTNS) generalize the notion of having low Schmidt-rank to multipartite quantum states. We study the task of testing whether an unknown pure state is a TTNS on $n$ qudits with bond dimension at most $r$. We also study the performance of tests using measurements performed on a small number of copies at a time.
  arXiv  Detail & Related papers  (2024-10-28T18:13:38Z)
• Testing multipartite productness is easier than testing bipartite productness [0.0]
  We show that $Omega(n / log n)$ copies are required (for fixed $epsilon leq frac12$) We discuss implications for testing graph states and computing the generalised geometric measure of entanglement.
  arXiv  Detail & Related papers  (2024-06-24T17:36:57Z)
• 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)
• Replicability in Reinforcement Learning [46.89386344741442]
  We focus on the fundamental setting of discounted MDPs with access to a generative model. Inspired by Impagliazzo et al. [2022], we say that an RL algorithm is replicable if, with high probability, it outputs the exact same policy after two executions.
  arXiv  Detail & Related papers  (2023-05-31T05:16:23Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• 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)
• Testing matrix product states [5.225550006603552]
  We study the problem of testing whether an unknown state $|psirangle$ is a matrix product state (MPS) in the property testing model. MPS are a class of physically-relevant quantum states which arise in the study of quantum many-body systems.
  arXiv  Detail & Related papers  (2022-01-05T21:10:50Z)
• Distributed quantum inner product estimation [14.222887950206658]
  A benchmarking task known as cross-platform verification has been proposed that aims to estimate the fidelity of states prepared on two quantum computers. No quantum communication can be performed between the two physical platforms due to hardware constraints. We show that the sample complexity must be at least $Omega(max1/varepsilon2,sqrtd/varepsilon)$, even in the strongest setting.
  arXiv  Detail & Related papers  (2021-11-05T05:35:03Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• The Power of Subsampling in Submodular Maximization [51.629656762796564]
  We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.
  arXiv  Detail & Related papers  (2021-04-06T20:25:57Z)
• Entanglement is Necessary for Optimal Quantum Property Testing [15.58122727889318]
  We show that with independent measurements, $Omega(d4/3/epsilon2)$ is necessary, even if the measurements are chosen adaptively. We develop several new techniques, including a chain-rule style proof of Paninski's lower bound for classical uniformity testing.
  arXiv  Detail & Related papers  (2020-04-16T18:28:39Z)
• 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.