10 papers
Hardness and Complexity Transition of Noisy Random Circuit Sampling
Byeongseon Go, Changhun Oh, Hyunseok Jeong
Random circuit sampling (RCS) is a leading candidate for demonstrating quantum advantage, supported by strong complexity-theoretic evidence of hardness in the ideal setting and by…
Virtual purification complements quantum error correction in quantum metrology
Hyukgun Kwon, Changhun Oh, Youngrong Lim +3
Quantum resources enable one to achieve quantum-enhanced estimation sensitivity beyond its classical counterpart. Many studies mainly focus on reducing statistical error, under the…
On computational complexity and average-case hardness of shallow-depth boson sampling
Byeongseon Go, Changhun Oh, Hyunseok Jeong
Boson sampling, a computational task believed to be classically hard to simulate, is expected to hold promise for demonstrating quantum computational advantage using near-term quan…
Advancing quantum imaging through learning theory
Yunkai Wang, Changhun Oh, Junyu Liu +2
We study quantum imaging by applying the resolvable expressive capacity (REC) formalism developed for physical neural networks (PNNs). In this paradigm of quantum learning, the ima…
Classical algorithms for estimating expectation values in linear-optical circuits
Youngrong Lim, Changhun Oh
We present a classical algorithm for approximating the expectation values of observables in linear-optical circuits with arbitrary product input states, achieving additive-error ac…
Sufficient conditions for hardness of lossy Gaussian boson sampling
Byeongseon Go, Changhun Oh, Hyunseok Jeong
Gaussian boson sampling (GBS) is a prominent candidate for the experimental demonstration of quantum advantage. However, while the current implementations of GBS are unavoidably su…