7 papers
A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
Xudong Wu, Guangxu Yang, Penghui Yao
We investigates a model of hybrid classical-quantum communication complexity, in which two parties first exchange classical messages and subsequently communicate using quantum mess…
On the Computational Complexity of Geometrically Local QAC0 circuits
Yangjing Dong, Fengning Ou, Penghui Yao
The computational complexity of , which are constant-depth, polynomial-size quantum circuit families consisting of arbitrary single-qubit unitaries and -qubit ge…
Experimental Efficient Influence Sampling of Quantum Processes
Hao Zhan, Zongbo Bao, Zekun Ye +4
Characterizing quantum processes is essential for unlocking the potential of quantum devices. However, standard quantum process tomography is resource-intensive and becomes infeasi…
Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing
Zongbo Bao, Yuxuan Liu, Penghui Yao +2
We consider the problem of deciding whether an -qubit unitary (or -bit Boolean function) is -close to some -junta or -far from every -junt…
Quantum and Classical Communication Complexity of Permutation-Invariant Functions
Ziyi Guan, Yunqi Huang, Penghui Yao +1
This paper gives a nearly tight characterization of the quantum communication complexity of the permutation-invariant Boolean functions. With such a characterization, we show that…
Distributed Quantum Simulation
Tianfeng Feng, Jue Xu, Wenjun Yu +3
Quantum simulation is a promising pathway toward practical quantum advantage by simulating large-scale quantum systems. In this work, we propose communication-efficient distributed…