Noise-tolerant parity learning with one quantum bit

Daniel K. Park, June Koo K. Rhee, Soonchil Lee

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


Demonstrating quantum advantage with less powerful but more realistic devices is of great importance in modern quantum information science. Recently, a significant quantum speedup was achieved in the problem of learning a hidden parity function with noise. However, if all data qubits at the query output are completely depolarized, the algorithm fails. In this work, we present a quantum parity learning algorithm that exhibits quantum advantage as long as one qubit is provided with nonzero polarization in each query. In this scenario, the quantum parity learning naturally becomes deterministic quantum computation with one qubit. Then the hidden parity function can be revealed by performing a set of operations that can be interpreted as measuring nonlocal observables on the auxiliary result qubit having nonzero polarization and each data qubit. We also discuss the source of the quantum advantage in our algorithm from the resource-theoretic point of view.

Original languageEnglish
Article number032327
JournalPhysical Review A
Issue number3
Publication statusPublished - 2018 Mar 20

Bibliographical note

Funding Information:
We thank Sumin Lim for helpful discussions. This research was supported by the National Research Foundation of Korea (Grants No. 2015R1A2A2A01006251 and No. 2016R1A5A1008184).

Publisher Copyright:
© 2018 American Physical Society.

All Science Journal Classification (ASJC) codes

  • Atomic and Molecular Physics, and Optics


Dive into the research topics of 'Noise-tolerant parity learning with one quantum bit'. Together they form a unique fingerprint.

Cite this