A Note on Enumeration by Fair Sampling

• URL: http://arxiv.org/abs/2104.01941v1
• Date: Mon, 5 Apr 2021 14:56:58 GMT
• Title: A Note on Enumeration by Fair Sampling
• Authors: Yuta Mizuno and Tamiki Komatsuzaki
• Abstract summary: This note describes an algorithm for enumerating all the elements in a finite set based on uniformly random sampling from the set. Our algorithm is based on a lemma of the coupon collector's problem and is an improved version of the algorithm described in arXiv:2007.08487 ( 2020)
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This note describes an algorithm for enumerating all the elements in a finite set based on uniformly random sampling from the set. This algorithm can be used for enumeration by fair sampling with quantum annealing. Our algorithm is based on a lemma of the coupon collector's problem and is an improved version of the algorithm described in arXiv:2007.08487 (2020). We provide a mathematical analysis and a numerical demonstration of our algorithm.

Related papers

• Random sampling of permutations through quantum circuits [0.0]
  We introduce classical algorithms for random sampling of permutations, drawing inspiration from the Steinhaus-Johnson-Trotter algorithm. We develop a quantum analogue of these classical algorithms using a quantum circuit model for random sampling of permutations for $n$-qubit systems.
  arXiv  Detail & Related papers  (2024-09-04T18:19:30Z)
• Bregman-divergence-based Arimoto-Blahut algorithm [53.64687146666141]
  We generalize the Arimoto-Blahut algorithm to a general function defined over Bregman-divergence system. We propose a convex-optimization-free algorithm that can be applied to classical and quantum rate-distortion theory.
  arXiv  Detail & Related papers  (2024-08-10T06:16:24Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  We study the problem of best-arm identification with fixed budget in multi-armed bandits with Bernoulli rewards. For the problem with two arms, also known as the A/B testing problem, we prove that there is no algorithm that performs as well as the algorithm sampling each arm equally.
  arXiv  Detail & Related papers  (2023-08-23T08:38:53Z)
• Quantum Algorithm for Path-Edge Sampling [0.9990687944474739]
  We present a quantum algorithm for sampling an edge on a path between two nodes s and t in an undirected graph given as an adjacency matrix. We use this path sampling algorithm as a subroutine for st-path finding and st-cut-set finding algorithms in some specific cases.
  arXiv  Detail & Related papers  (2023-03-06T17:45:12Z)
• Reflection-Based Adiabatic State Preparation [0.0]
  Our algorithm deploys a sequence of reflections determined from eigenspaces of instantaneous Hamiltonians defined along an adiabatic schedule. We provide numerical evidence suggesting that, for search problems, our algorithm can find a solution faster, on average, than Grover's search.
  arXiv  Detail & Related papers  (2021-11-10T00:03:00Z)
• Estimating leverage scores via rank revealing methods and randomization [50.591267188664666]
  We study algorithms for estimating the statistical leverage scores of rectangular dense or sparse matrices of arbitrary rank. Our approach is based on combining rank revealing methods with compositions of dense and sparse randomized dimensionality reduction transforms.
  arXiv  Detail & Related papers  (2021-05-23T19:21:55Z)
• Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
  We give a row sampling algorithm for the quantile loss function with sample complexity nearly linear in the dimensionality of the data. Based upon our row sampling algorithm, we give the fastest known algorithm for quantile regression and a graph sparsification algorithm for balanced directed graphs.
  arXiv  Detail & Related papers  (2020-06-15T13:40:07Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)
• Quantum Sampling Algorithms for Near-Term Devices [0.0]
  We introduce a family of quantum algorithms that provide unbiased samples by encoding the entire Gibbs distribution. We show that this approach leads to a speedup over a classical Markov chain algorithm. It opens the door to exploring potentially useful sampling algorithms on near-term quantum devices.
  arXiv  Detail & Related papers  (2020-05-28T14:46:20Z)
• Active Model Estimation in Markov Decision Processes [108.46146218973189]
  We study the problem of efficient exploration in order to learn an accurate model of an environment, modeled as a Markov decision process (MDP) We show that our Markov-based algorithm outperforms both our original algorithm and the maximum entropy algorithm in the small sample regime.
  arXiv  Detail & Related papers  (2020-03-06T16:17:24Z)

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.