Learning DNFs under product distributions via μ-biased quantum Fourier sampling

Learning DNFs under product distributions via μ-biased quantum Fourier sampling

We show that DNF formulae can be quantum PAC-learned in polynomial time under product distributions using a quantum example oracle. The current best classical algorithm runs in superpolynomial time. Our result extends the work by Bshouty and Jackson (1998) that proved that DNF formulae are efficient...

Cur síos iomlán

Sonraí bibleagrafaíochta
Príomhchruthaitheoirí:	Kanade, V, Rocchetto, A, Severini, S
Formáid:	Journal article
Teanga:	English
Foilsithe / Cruthaithe:	Rinton Press 2019

Míreanna comhchosúla

Learning hard quantum distributions with variational autoencoders
de réir: Rocchetto, A, et al.
Foilsithe / Cruthaithe: (2018)

Modelling non-markovian quantum processes with recurrent neural networks
de réir: Banchi, L, et al.
Foilsithe / Cruthaithe: (2018)

Modelling non-markovian quantum processes with recurrent neural networks
de réir: Leonardo Banchi, et al.
Foilsithe / Cruthaithe: (2018-01-01)

Experimental learning of quantum states
de réir: Rocchetto, A, et al.
Foilsithe / Cruthaithe: (2019)

Algorithmic models in quantum mechanics
de réir: Rocchetto, A
Foilsithe / Cruthaithe: (2019)

Quantum Computation via Multiport Discretized Quantum Fourier Optical Processors
de réir: Mohammad Rezai, et al.
Foilsithe / Cruthaithe: (2024-01-01)

Synthesis and Evaluation of Novel Biased μ-Opioid-Receptor (μOR) Agonists
de réir: Mengjun Ma, et al.
Foilsithe / Cruthaithe: (2019-01-01)

More on the quantum harmonic oscillator via unilateral Fourier transform
de réir: Douglas Willian Vieira, et al.
Foilsithe / Cruthaithe: (2022-05-01)

A Robust Framework for Distributional Shift Detection Under Sample-Bias
de réir: Birk Torpmann-Hagen, et al.
Foilsithe / Cruthaithe: (2024-01-01)

The quantum Fourier transform and quantum chaos
de réir: Weinstein, Yaakov Shmuel, 1974-
Foilsithe / Cruthaithe: (2005)

Quantum Fourier transform for nanoscale quantum sensing
de réir: Vadim Vorobyov, et al.
Foilsithe / Cruthaithe: (2021-08-01)

Fundamentals of Quantum Fourier Optics
de réir: Mohammad Rezai, et al.
Foilsithe / Cruthaithe: (2023-01-01)

Fourier-transforming with quantum annealers
de réir: Itay eHen
Foilsithe / Cruthaithe: (2014-07-01)

Fourier Quantum Process Tomography
de réir: Francesco Di Colandrea, et al.
Foilsithe / Cruthaithe: (2024-05-01)

Research on Discrete Fourier Transform-Based Phasor Measurement Algorithm for Distribution Network under High Frequency Sampling
de réir: Zhiguo Zhou, et al.
Foilsithe / Cruthaithe: (2018-08-01)

Investigation of Microplastics (≥10 μm) in Meconium by Fourier Transform Infrared Microspectroscopy
de réir: Zhiming Li, et al.
Foilsithe / Cruthaithe: (2023-03-01)

Quantum states of a particle in a box via unilateral Fourier transform
de réir: Douglas W. Vieira, et al.
Foilsithe / Cruthaithe: (2020-06-01)

Sparse recovery and Fourier sampling
de réir: Price, Eric C
Foilsithe / Cruthaithe: (2014)

Simplicity bias in transformers and their ability to learn sparse boolean functions
de réir: Bhattamishra, S, et al.
Foilsithe / Cruthaithe: (2023)

Digital-analog quantum algorithm for the quantum Fourier transform
de réir: Ana Martin, et al.
Foilsithe / Cruthaithe: (2020-01-01)

Improving application performance with biased distributions of quantum states
de réir: Sanjaya Lohani, et al.
Foilsithe / Cruthaithe: (2021-11-01)

Approximate quantum Fourier transform and decoherence.
de réir: Barenco, A, et al.
Foilsithe / Cruthaithe: (1996)

Approximate Quantum Fourier Transform and Decoherence
de réir: Barenco, A, et al.
Foilsithe / Cruthaithe: (1996)

Quantum Weighted Fractional Fourier Transform
de réir: Tieyu Zhao, et al.
Foilsithe / Cruthaithe: (2022-06-01)

Circuit of Quantum Fractional Fourier Transform
de réir: Tieyu Zhao, et al.
Foilsithe / Cruthaithe: (2023-10-01)

The Fourier Transform on Quantum Euclidean Space
de réir: Kevin Coulembier
Foilsithe / Cruthaithe: (2011-05-01)

Quantum self-learning Monte Carlo and quantum-inspired Fourier transform sampler
de réir: Katsuhiro Endo, et al.
Foilsithe / Cruthaithe: (2020-12-01)

On the Bias of Precision Estimation Under Separate Sampling
de réir: Shuilian Xie, et al.
Foilsithe / Cruthaithe: (2019-07-01)

Optimization of Sampling Mode in Macro Fourier Ptychography Imaging Based on Energy Distribution
de réir: Runbo Jiang, et al.
Foilsithe / Cruthaithe: (2023-03-01)

Distributions and Fourier transforms /
de réir: 315367 Donoghue, William F.
Foilsithe / Cruthaithe: (1969)

Electric circuits for universal quantum gates and quantum Fourier transformation
de réir: Motohiko Ezawa
Foilsithe / Cruthaithe: (2020-06-01)

Quantum Voting Protocol Based on Quantum Fourier Transform Summation
de réir: FENG Yan, WANG Rui-cong
Foilsithe / Cruthaithe: (2022-05-01)

Sample-Optimal Fourier Sampling in Any Constant Dimension
de réir: Indyk, Piotr, et al.
Foilsithe / Cruthaithe: (2017)

A Fourier transform for the quantum Toda lattice
de réir: Lonergan, Gus
Foilsithe / Cruthaithe: (2021)

Quantum Fourier Transform Has Small Entanglement
de réir: Jielun Chen (陈捷伦), et al.
Foilsithe / Cruthaithe: (2023-10-01)

Quantum Fourier transform to estimate drive cycles
de réir: Vinayak Dixit, et al.
Foilsithe / Cruthaithe: (2022-01-01)

Assessing the effect of sample bias correction in species distribution models
de réir: Nicolas Dubos, et al.
Foilsithe / Cruthaithe: (2022-12-01)

Fourier transforms and the theory of distributions /
de réir: 353117 Arsac, Jacques, et al.
Foilsithe / Cruthaithe: (1966)

On the regularizations Fourier series of distributions
de réir: Rakhimov, Abdumalik
Foilsithe / Cruthaithe: (2011)

Understanding holographic error correction via unique algebras and atomic examples
de réir: Jason Pollack, et al.
Foilsithe / Cruthaithe: (2022-06-01)