Towards Optimizing the Expected Performance of Sampling-Based Quantum-Inspired Algorithms

• URL: http://arxiv.org/abs/2501.05184v2
• Date: Tue, 14 Jan 2025 09:38:04 GMT
• Title: Towards Optimizing the Expected Performance of Sampling-Based Quantum-Inspired Algorithms
• Abstract summary: We analyze two major subroutines in sampling-based quantum-inspired algorithms.<n>We discuss their possible improvements by generalizing the data structure.<n>We expect our findings to suggest optimal implementations for various quantum and quantum-inspired machine learning algorithms.
• Score: 4.513787113118679
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Quantum-inspired classical algorithms has received much attention due to its exponential speedup compared to existing algorithms, under certain data storage assumptions. The improvements are noticeable in fundamental linear algebra tasks. In this work, we analyze two major subroutines in sampling-based quantum-inspired algorithms, specifically, inner product estimation and sampling from a linear combination of vectors, and discuss their possible improvements by generalizing the data structure. The idea is to consider the average behavior of the subroutines under certain assumptions regarding the data elements. This allows us to determine the optimal data structure, and the high-dimensional nature of data makes our assumptions reasonable. Experimental results from recommendation systems also highlight a consistent preference for our proposed data structure. Motivated by this observation, we tighten the upper bound on the number of required measurements for direct fidelity estimation. We expect our findings to suggest optimal implementations for various quantum and quantum-inspired machine learning algorithms that involve extremely high-dimensional operations, which has potential for many applications.

Related papers

• Bayesian Optimization with Structured Measurements: A Vector-Valued RKHS Framework [10.074327344317116]
  We study Bayesian optimization over a vector-valued operator with structured measurements.<n>This allows each observation to reveal substantially richer information about the underlying system.<n>We propose an algorithm based on the upper confidence bound (UCB) acquisition function with regret guarantees.
  arXiv  Detail & Related papers  (2026-05-10T21:48:09Z)
• Does Weighting Improve Matrix Factorization for Recommender Systems? [36.1332376112504]
  Matrix factorization is a widely used approach for top-N recommendation and collaborative filtering.<n>In this paper, we conduct a systematic study of various weighting schemes and matrix factorization algorithms.<n>We find that training with unweighted data can perform comparably to, and sometimes outperform, training with weighted data, especially for large models.
  arXiv  Detail & Related papers  (2025-10-12T04:15:24Z)
• Unrolled denoising networks provably learn optimal Bayesian inference [54.79172096306631]
  We prove the first rigorous learning guarantees for neural networks based on unrolling approximate message passing (AMP) For compressed sensing, we prove that when trained on data drawn from a product prior, the layers of the network converge to the same denoisers used in Bayes AMP.
  arXiv  Detail & Related papers  (2024-09-19T17:56:16Z)
• Benchmarking Optimizers for Qumode State Preparation with Variational Quantum Algorithms [10.941053143198092]
  There has been a growing interest in qumodes due to advancements in the field and their potential applications. This paper aims to bridge this gap by providing performance benchmarks of various parameters used in state preparation with Variational Quantum Algorithms.
  arXiv  Detail & Related papers  (2024-05-07T17:15:58Z)
• Optimization of a Hydrodynamic Computational Reservoir through Evolution [58.720142291102135]
  We interface with a model of a hydrodynamic system, under development by a startup, as a computational reservoir. We optimized the readout times and how inputs are mapped to the wave amplitude or frequency using an evolutionary search algorithm. Applying evolutionary methods to this reservoir system substantially improved separability on an XNOR task, in comparison to implementations with hand-selected parameters.
  arXiv  Detail & Related papers  (2023-04-20T19:15:02Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  Quantum computing can empower machine learning models by enabling kernel machines to leverage quantum kernels for representing similarity measures between data.<n>We present an approach to this problem, which employs optimization techniques, similar to those used in neural architecture search and AutoML.<n>The results obtained by testing our approach on a high-energy physics problem demonstrate that, in the best-case scenario, we can either match or improve testing accuracy with respect to the manual design approach.
  arXiv  Detail & Related papers  (2022-09-22T16:42:14Z)
• 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)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Expectation propagation on the diluted Bayesian classifier [0.0]
  We introduce a statistical mechanics inspired strategy that addresses the problem of sparse feature selection in the context of binary classification. A computational scheme known as expectation propagation (EP) is used to train a continuous-weights perceptron learning a classification rule. EP is a robust and competitive algorithm in terms of variable selection properties, estimation accuracy and computational complexity.
  arXiv  Detail & Related papers  (2020-09-20T23:59:44Z)
• Sequential Subspace Search for Functional Bayesian Optimization Incorporating Experimenter Intuition [63.011641517977644]
  Our algorithm generates a sequence of finite-dimensional random subspaces of functional space spanned by a set of draws from the experimenter's Gaussian Process. Standard Bayesian optimisation is applied on each subspace, and the best solution found used as a starting point (origin) for the next subspace. We test our algorithm in simulated and real-world experiments, namely blind function matching, finding the optimal precipitation-strengthening function for an aluminium alloy, and learning rate schedule optimisation for deep networks.
  arXiv  Detail & Related papers  (2020-09-08T06:54:11Z)
• Frequency Estimation in Data Streams: Learning the Optimal Hashing Scheme [3.7565501074323224]
  We present a novel approach for the problem of frequency estimation in data streams that is based on optimization and machine learning. The proposed approach exploits an observed stream prefix to near-optimally hash elements and compress the target frequency distribution. We show that the proposed approach outperforms existing approaches by one to two orders of magnitude in terms of its average (per element) estimation error and by 45-90% in terms of its expected magnitude of estimation error.
  arXiv  Detail & Related papers  (2020-07-17T22:15:22Z)

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.