5 papers
Linear-Size QAC0 Channels: Learning, Testing and Hardness
Yangjing Dong, Fengning Ou, Penghui Yao
Shallow quantum circuits have attracted increasing attention in recent years, due to the fact that current noisy quantum hardware can only perform faithful quantum computation for…
Optimal quantum sampling on distributed databases
Longyun Chen, Jingcheng Liu, Penghui Yao
Quantum sampling, a fundamental subroutine in numerous quantum algorithms, involves encoding a given probability distribution in the amplitudes of a pure state. Given the hefty cos…
On the Computational Power of QAC0 with Barely Superlinear Ancillae
Anurag Anshu, Yangjing Dong, Fengning Ou +1
is the family of constant-depth polynomial-size quantum circuits consisting of arbitrary single qubit unitaries and multi-qubit Toffoli gates. It was introduced by…
Almost Optimal Algorithms for Token Collision in Anonymous Networks
Sirui Bai, Xinyu Fu, Xudong Wu +2
In distributed systems, situations often arise where some nodes each holds a collection of tokens, and all nodes collectively need to determine whether all tokens are distinct. For…
Communication Complexity of Common Randomness Generation with Isotropic States
Yangjing Dong, Penghui Yao
This paper addresses the problem of generating a common random string with min-entropy k using an unlimited supply of noisy EPR pairs or quantum isotropic states, with minimal comm…