Related papers: Continuous LWE

Continuous LWE

URL: http://arxiv.org/abs/2005.09595v2
Date: Sat, 24 Oct 2020 20:55:35 GMT
Title: Continuous LWE
Authors: Joan Bruna, Oded Regev, Min Jae Song, and Yi Tang
Abstract summary: We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE.
Score: 32.345218864470446
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues of (quantum) attacks on lattice problems. Our work resolves an open problem regarding the computational complexity of learning mixtures of Gaussians without separability assumptions (Diakonikolas 2016, Moitra 2018). As an additional motivation, (a slight variant of) CLWE was considered in the context of robust machine learning (Diakonikolas et al.~FOCS 2017), where hardness in the statistical query (SQ) model was shown; our work addresses the open question regarding its computational hardness (Bubeck et al.~ICML 2019).

Related papers

Solving for X and Beyond: Can Large Language Models Solve Complex Math Problems with More-Than-Two Unknowns? [57.80779199039929]
Large Language Models (LLMs) have demonstrated remarkable performance in solving math problems. This paper introduces a novel benchmark, BeyondX, designed to address these limitations by incorporating problems with multiple unknowns. Empirical study on BeyondX reveals that the performance of existing LLMs, even those fine-tuned specifically on math tasks, significantly decreases as the number of unknowns increases.
arXiv Detail & Related papers (2024-07-06T17:01:04Z)
Investigating the Relation Between Problem Hardness and QUBO Properties [0.0]
This work aims to shed some light on the relationship between the problems' properties. We analyze two well-known problems from Machine Learning, namely Clustering and Support Vector Machine (SVM) training. An empirical evaluation provides interesting insights, showing that the spectral gap of Clustering QUBO instances positively correlates with data separability, while for SVM QUBO the opposite is true.
arXiv Detail & Related papers (2024-04-03T13:53:03Z)
Clique Homology is QMA1-hard [0.0]
We show that the decision problem of determining homology groups of simplicial complexes is QMA1-hard. This suggests that the seemingly classical problem may in fact be quantum mechanical. We discuss potential implications for the problem of quantum advantage in topological data analysis.
arXiv Detail & Related papers (2022-09-23T18:14:16Z)
Beyond Supervised Continual Learning: a Review [69.9674326582747]
Continual Learning (CL) is a flavor of machine learning where the usual assumption of stationary data distribution is relaxed or omitted. Changes in the data distribution can cause the so-called catastrophic forgetting (CF) effect: an abrupt loss of previous knowledge. This article reviews literature that study CL in other settings, such as learning with reduced supervision, fully unsupervised learning, and reinforcement learning.
arXiv Detail & Related papers (2022-08-30T14:44:41Z)
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures [11.348971335676444]
We show direct and conceptually simple reductions between the classical learning with errors problem and its continuous analog, CLWE. This allows us to bring to bear the powerful of LWE-based cryptography to the applications of CLWE.
arXiv Detail & Related papers (2022-04-06T03:03:39Z)
Oracle separations of hybrid quantum-classical circuits [68.96380145211093]
Two models of quantum computation: CQ_d and QC_d. CQ_d captures the scenario of a d-depth quantum computer many times; QC_d is more analogous to measurement-based quantum computation. We show that, despite the similarities between CQ_d and QC_d, the two models are intrinsically, i.e. CQ_d $nsubseteq$ QC_d and QC_d $nsubseteq$ CQ_d relative to an oracle.
arXiv Detail & Related papers (2022-01-06T03:10:53Z)
Lattice-Based Methods Surpass Sum-of-Squares in Clustering [98.46302040220395]
Clustering is a fundamental primitive in unsupervised learning. Recent work has established lower bounds against the class of low-degree methods. We show that, perhaps surprisingly, this particular clustering model textitdoes not exhibit a statistical-to-computational gap.
arXiv Detail & Related papers (2021-12-07T18:50:17Z)
Quantum Algorithms for Variants of Average-Case Lattice Problems via Filtering [13.70673475846529]
We show-time quantum algorithms for the following problems. Our main contribution is solving LWE given LWE-like quantum states with interesting parameters using a filtering technique.
arXiv Detail & Related papers (2021-08-25T02:23:37Z)
A New Constructive Heuristic driven by Machine Learning for the Traveling Salesman Problem [8.604882842499212]
Recent systems applying Machine Learning (ML) to solve the Traveling Salesman Problem (TSP) exhibit issues when they try to scale up to real case scenarios. The use of Candidate Lists (CLs) has been brought up to cope with the issues. In this work we instead use a machine learning model to confirm the addition in the solution just for high probable edges.
arXiv Detail & Related papers (2021-08-17T21:37:23Z)
Disentangling Observed Causal Effects from Latent Confounders using Method of Moments [67.27068846108047]
We provide guarantees on identifiability and learnability under mild assumptions. We develop efficient algorithms based on coupled tensor decomposition with linear constraints to obtain scalable and guaranteed solutions.
arXiv Detail & Related papers (2021-01-17T07:48:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.