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...

書誌詳細
主要な著者:	Kanade, V, Rocchetto, A, Severini, S
フォーマット:	Journal article
言語:	English
出版事項:	Rinton Press 2019

類似資料

Learning hard quantum distributions with variational autoencoders
著者:: Rocchetto, A, 等
出版事項: (2018)

Modelling non-markovian quantum processes with recurrent neural networks
著者:: Banchi, L, 等
出版事項: (2018)

Modelling non-markovian quantum processes with recurrent neural networks
著者:: Leonardo Banchi, 等
出版事項: (2018-01-01)

Experimental learning of quantum states
著者:: Rocchetto, A, 等
出版事項: (2019)

Algorithmic models in quantum mechanics
著者:: Rocchetto, A
出版事項: (2019)

Quantum Computation via Multiport Discretized Quantum Fourier Optical Processors
著者:: Mohammad Rezai, 等
出版事項: (2024-01-01)

Synthesis and Evaluation of Novel Biased μ-Opioid-Receptor (μOR) Agonists
著者:: Mengjun Ma, 等
出版事項: (2019-01-01)

More on the quantum harmonic oscillator via unilateral Fourier transform
著者:: Douglas Willian Vieira, 等
出版事項: (2022-05-01)

A Robust Framework for Distributional Shift Detection Under Sample-Bias
著者:: Birk Torpmann-Hagen, 等
出版事項: (2024-01-01)

The quantum Fourier transform and quantum chaos
著者:: Weinstein, Yaakov Shmuel, 1974-
出版事項: (2005)

Quantum Fourier transform for nanoscale quantum sensing
著者:: Vadim Vorobyov, 等
出版事項: (2021-08-01)

Fundamentals of Quantum Fourier Optics
著者:: Mohammad Rezai, 等
出版事項: (2023-01-01)

Fourier-transforming with quantum annealers
著者:: Itay eHen
出版事項: (2014-07-01)

Fourier Quantum Process Tomography
著者:: Francesco Di Colandrea, 等
出版事項: (2024-05-01)

Research on Discrete Fourier Transform-Based Phasor Measurement Algorithm for Distribution Network under High Frequency Sampling
著者:: Zhiguo Zhou, 等
出版事項: (2018-08-01)

Investigation of Microplastics (≥10 μm) in Meconium by Fourier Transform Infrared Microspectroscopy
著者:: Zhiming Li, 等
出版事項: (2023-03-01)

Quantum states of a particle in a box via unilateral Fourier transform
著者:: Douglas W. Vieira, 等
出版事項: (2020-06-01)

Sparse recovery and Fourier sampling
著者:: Price, Eric C
出版事項: (2014)

Simplicity bias in transformers and their ability to learn sparse boolean functions
著者:: Bhattamishra, S, 等
出版事項: (2023)

Digital-analog quantum algorithm for the quantum Fourier transform
著者:: Ana Martin, 等
出版事項: (2020-01-01)

Improving application performance with biased distributions of quantum states
著者:: Sanjaya Lohani, 等
出版事項: (2021-11-01)

Approximate quantum Fourier transform and decoherence.
著者:: Barenco, A, 等
出版事項: (1996)

Approximate Quantum Fourier Transform and Decoherence
著者:: Barenco, A, 等
出版事項: (1996)

Quantum Weighted Fractional Fourier Transform
著者:: Tieyu Zhao, 等
出版事項: (2022-06-01)

Circuit of Quantum Fractional Fourier Transform
著者:: Tieyu Zhao, 等
出版事項: (2023-10-01)

The Fourier Transform on Quantum Euclidean Space
著者:: Kevin Coulembier
出版事項: (2011-05-01)

Quantum self-learning Monte Carlo and quantum-inspired Fourier transform sampler
著者:: Katsuhiro Endo, 等
出版事項: (2020-12-01)

On the Bias of Precision Estimation Under Separate Sampling
著者:: Shuilian Xie, 等
出版事項: (2019-07-01)

Optimization of Sampling Mode in Macro Fourier Ptychography Imaging Based on Energy Distribution
著者:: Runbo Jiang, 等
出版事項: (2023-03-01)

Distributions and Fourier transforms /
著者:: 315367 Donoghue, William F.
出版事項: (1969)

Electric circuits for universal quantum gates and quantum Fourier transformation
著者:: Motohiko Ezawa
出版事項: (2020-06-01)

Quantum Voting Protocol Based on Quantum Fourier Transform Summation
著者:: FENG Yan, WANG Rui-cong
出版事項: (2022-05-01)

Sample-Optimal Fourier Sampling in Any Constant Dimension
著者:: Indyk, Piotr, 等
出版事項: (2017)

A Fourier transform for the quantum Toda lattice
著者:: Lonergan, Gus
出版事項: (2021)

Quantum Fourier Transform Has Small Entanglement
著者:: Jielun Chen (陈捷伦), 等
出版事項: (2023-10-01)

Quantum Fourier transform to estimate drive cycles
著者:: Vinayak Dixit, 等
出版事項: (2022-01-01)

Assessing the effect of sample bias correction in species distribution models
著者:: Nicolas Dubos, 等
出版事項: (2022-12-01)

Fourier transforms and the theory of distributions /
著者:: 353117 Arsac, Jacques, 等
出版事項: (1966)

On the regularizations Fourier series of distributions
著者:: Rakhimov, Abdumalik
出版事項: (2011)

Understanding holographic error correction via unique algebras and atomic examples
著者:: Jason Pollack, 等
出版事項: (2022-06-01)