Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity

• URL: http://arxiv.org/abs/2502.08721v1
• Date: Wed, 12 Feb 2025 19:00:10 GMT
• Title: Complement Sampling: Provable, Verifiable and NISQable Quantum Advantage in Sample Complexity
• Authors: Marcello Benedetti, Harry Buhrman, Jordi Weggemans,
• Abstract summary: We give a simple quantum algorithm that uses only a single quantum sample -- a single copy of the uniform superposition over elements of the subset. In a sample-to-sample setting, quantum computation can achieve the largest possible separation over classical computation.
• Score: 0.0
• License:
• Abstract: Consider a fixed universe of $N=2^n$ elements and the uniform distribution over elements of some subset of size $K$. Given samples from this distribution, the task of complement sampling is to provide a sample from the complementary subset. We give a simple quantum algorithm that uses only a single quantum sample -- a single copy of the uniform superposition over elements of the subset. When $K=N/2$, we show that the quantum algorithm succeeds with probability $1$, whereas classically $\Theta(N)$ samples are required to succeed with bounded probability of error. This shows that in a sample-to-sample setting, quantum computation can achieve the largest possible separation over classical computation. Moreover, we show that the same bound can be lifted to prove average-case hardness. It follows that under the assumption of the existence of one-way functions, complement sampling gives provable, verifiable and NISQable quantum advantage in a sample complexity setting.

Related papers

• 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)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
  arXiv  Detail & Related papers  (2023-10-17T17:55:32Z)
• Sampled Transformer for Point Sets [80.66097006145999]
  sparse transformer can reduce the computational complexity of the self-attention layers to $O(n)$, whilst still being a universal approximator of continuous sequence-to-sequence functions. We propose an $O(n)$ complexity sampled transformer that can process point set elements directly without any additional inductive bias.
  arXiv  Detail & Related papers  (2023-02-28T06:38:05Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  Social and real-world considerations have given rise to multi-distribution learning paradigms. We establish the optimal sample complexity of these learning paradigms and give algorithms that meet this sample complexity. Our algorithm design and analysis are enabled by our extensions of online learning techniques for solving zero-sum games.
  arXiv  Detail & Related papers  (2022-10-22T19:07:26Z)
• Quantum supremacy with spin squeezed atomic ensembles [0.0]
  We propose a method to achieve quantum supremacy using ensembles of qubits. Each ensemble is assumed to be controllable only with its total spin. We show that the probability distribution of the final measurements quickly approaches a Porter-Thomas distribution.
  arXiv  Detail & Related papers  (2022-04-25T16:42:37Z)
• Uncorrelated problem-specific samples of quantum states from zero-mean Wishart distributions [4.289102530380288]
  We present a two-step algorithm for sampling from the quantum state space. We establish the explicit form of the induced Wishart distribution for quantum states. We demonstrate that this sampling algorithm is very efficient for one-qubit and two-qubit states, and reasonably efficient for three-qubit states.
  arXiv  Detail & Related papers  (2021-06-16T03:06:41Z)
• Learning k-qubit Quantum Operators via Pauli Decomposition [11.498089180181365]
  Motivated by the limited qubit capacity of current quantum systems, we study the quantum sample complexity of $k$-qubit quantum operators. We show that the quantum sample complexity of $k$-qubit quantum operations is comparable to the classical sample complexity of their counterparts.
  arXiv  Detail & Related papers  (2021-02-10T01:20:55Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)
• 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.