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

Fuld beskrivelse

Bibliografiske detaljer
Main Authors:	Kanade, V, Rocchetto, A, Severini, S
Format:	Journal article
Sprog:	English
Udgivet:	Rinton Press 2019

Lignende værker

Learning hard quantum distributions with variational autoencoders
af: Rocchetto, A, et al.
Udgivet: (2018)

Modelling non-markovian quantum processes with recurrent neural networks
af: Banchi, L, et al.
Udgivet: (2018)

Modelling non-markovian quantum processes with recurrent neural networks
af: Leonardo Banchi, et al.
Udgivet: (2018-01-01)

Experimental learning of quantum states
af: Rocchetto, A, et al.
Udgivet: (2019)

Algorithmic models in quantum mechanics
af: Rocchetto, A
Udgivet: (2019)

Quantum Computation via Multiport Discretized Quantum Fourier Optical Processors
af: Mohammad Rezai, et al.
Udgivet: (2024-01-01)

Synthesis and Evaluation of Novel Biased μ-Opioid-Receptor (μOR) Agonists
af: Mengjun Ma, et al.
Udgivet: (2019-01-01)

More on the quantum harmonic oscillator via unilateral Fourier transform
af: Douglas Willian Vieira, et al.
Udgivet: (2022-05-01)

A Robust Framework for Distributional Shift Detection Under Sample-Bias
af: Birk Torpmann-Hagen, et al.
Udgivet: (2024-01-01)

The quantum Fourier transform and quantum chaos
af: Weinstein, Yaakov Shmuel, 1974-
Udgivet: (2005)

Quantum Fourier transform for nanoscale quantum sensing
af: Vadim Vorobyov, et al.
Udgivet: (2021-08-01)

Fundamentals of Quantum Fourier Optics
af: Mohammad Rezai, et al.
Udgivet: (2023-01-01)

Fourier-transforming with quantum annealers
af: Itay eHen
Udgivet: (2014-07-01)

Fourier Quantum Process Tomography
af: Francesco Di Colandrea, et al.
Udgivet: (2024-05-01)

Research on Discrete Fourier Transform-Based Phasor Measurement Algorithm for Distribution Network under High Frequency Sampling
af: Zhiguo Zhou, et al.
Udgivet: (2018-08-01)

Investigation of Microplastics (≥10 μm) in Meconium by Fourier Transform Infrared Microspectroscopy
af: Zhiming Li, et al.
Udgivet: (2023-03-01)

Quantum states of a particle in a box via unilateral Fourier transform
af: Douglas W. Vieira, et al.
Udgivet: (2020-06-01)

Sparse recovery and Fourier sampling
af: Price, Eric C
Udgivet: (2014)

Simplicity bias in transformers and their ability to learn sparse boolean functions
af: Bhattamishra, S, et al.
Udgivet: (2023)

Digital-analog quantum algorithm for the quantum Fourier transform
af: Ana Martin, et al.
Udgivet: (2020-01-01)

Improving application performance with biased distributions of quantum states
af: Sanjaya Lohani, et al.
Udgivet: (2021-11-01)

Approximate quantum Fourier transform and decoherence.
af: Barenco, A, et al.
Udgivet: (1996)

Approximate Quantum Fourier Transform and Decoherence
af: Barenco, A, et al.
Udgivet: (1996)

Quantum Weighted Fractional Fourier Transform
af: Tieyu Zhao, et al.
Udgivet: (2022-06-01)

Circuit of Quantum Fractional Fourier Transform
af: Tieyu Zhao, et al.
Udgivet: (2023-10-01)

The Fourier Transform on Quantum Euclidean Space
af: Kevin Coulembier
Udgivet: (2011-05-01)

Quantum self-learning Monte Carlo and quantum-inspired Fourier transform sampler
af: Katsuhiro Endo, et al.
Udgivet: (2020-12-01)

On the Bias of Precision Estimation Under Separate Sampling
af: Shuilian Xie, et al.
Udgivet: (2019-07-01)

Optimization of Sampling Mode in Macro Fourier Ptychography Imaging Based on Energy Distribution
af: Runbo Jiang, et al.
Udgivet: (2023-03-01)

Distributions and Fourier transforms /
af: 315367 Donoghue, William F.
Udgivet: (1969)

Electric circuits for universal quantum gates and quantum Fourier transformation
af: Motohiko Ezawa
Udgivet: (2020-06-01)

Quantum Voting Protocol Based on Quantum Fourier Transform Summation
af: FENG Yan, WANG Rui-cong
Udgivet: (2022-05-01)

Sample-Optimal Fourier Sampling in Any Constant Dimension
af: Indyk, Piotr, et al.
Udgivet: (2017)

A Fourier transform for the quantum Toda lattice
af: Lonergan, Gus
Udgivet: (2021)

Quantum Fourier Transform Has Small Entanglement
af: Jielun Chen (陈捷伦), et al.
Udgivet: (2023-10-01)

Quantum Fourier transform to estimate drive cycles
af: Vinayak Dixit, et al.
Udgivet: (2022-01-01)

Assessing the effect of sample bias correction in species distribution models
af: Nicolas Dubos, et al.
Udgivet: (2022-12-01)

Fourier transforms and the theory of distributions /
af: 353117 Arsac, Jacques, et al.
Udgivet: (1966)

On the regularizations Fourier series of distributions
af: Rakhimov, Abdumalik
Udgivet: (2011)

Understanding holographic error correction via unique algebras and atomic examples
af: Jason Pollack, et al.
Udgivet: (2022-06-01)