Quantum Advantage in Learning Parity with Noise
Daniel Kyungdeock Park, Korea Advanced Institute of Science and Technology
Machine learning is an interesting family of problems for which near-term quantum devices can provide considerable advantages. In particular, exponential quantum speedup is recently demonstrated in learning a Boolean function that calculates the parity of a randomly chosen input bit string and a hidden bit string in the presence of noise, the problem known as learning parity with noise (LPN).