1 citations · 1 across the 7 of their papers we have counts for
12 papers
Quantum Submodular Maximization
Yonggang Jiang, Xiaoming Sun, Penghui Yao +3
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constr…
Toward Optimal Circuit Depth for Geometrically Local Hamiltonian Simulation
Zhenyu Shen, Zheyu Shen, Yusen Wu +3
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation s…
Classical Algorithms for Function Computation in Gaussian Boson Sampling
Ruoting Dou, Hao Zhan, Shengjun Wu +2
Gaussian boson sampling (GBS) seeks quantum advantage by sampling photon-number patterns generated with squeezed inputs and passive linear optics. Many proposed GBS applications in…
Optimal Quantum Junta Testing without Inverse Queries
Jinge Bao, Minbo Gao, Penghui Yao
We study the query complexity of testing quantum juntas. Given an unknown -qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most qu…
On the Computational Power of Geometrically Local QAC circuits
Yangjing Dong, Fengning Ou, Penghui Yao
The computational power of , which are constant-depth quantum circuit families consisting of arbitrary single-qubit unitaries and n-qubit generalized Toffoli gates, h…
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…
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…
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…
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…
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…
On the Fine-Grained Query Complexity of Symmetric Functions
Supartha Podder, Penghui Yao, Zekun Ye
This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to . Our con…
On the exact quantum query complexity of and
Penghui Yao, Zekun Ye
The query model has generated considerable interest in both classical and quantum computing communities. Typically, quantum advantages are demonstrated by showcasing a quantum algo…