22 citations · 61 across the 11 of their papers we have counts for
14 papers
Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
Zekun Ye
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most nonzero Fourier coefficients. We give a learner with near-optimal $\wide…
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…
Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
Yunqi Huang, Zekun Ye
We study how symmetry affects quantum advantage in two-party communication complexity. For any partial function on length- strings over a fixed alphabet of size , invaria…
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…
Deterministic Algorithms for the Hidden Subgroup Problem
Zekun Ye, Lvzhou Li
We consider deterministic algorithms for the well-known hidden subgroup problem (): for a finite group and a finite set , given a function and the…
Towards Plug-and-Play Visual Graph Query Interfaces: Data-driven Canned Pattern Selection for Large Networks
Zifeng Yuan, Huey Eng Chua, Sourav S Bhowmick +3
Canned patterns (i.e. small subgraph patterns) in visual graph query interfaces (a.k.a GUI) facilitate efficient query formulation by enabling pattern-at-a-time construction mode.…
Sample complexity of hidden subgroup problem
Zekun Ye, Lvzhou Li
The hidden subgroup problem () has been attracting much attention in quantum computing, since several well-known quantum algorithms including Shor algorithm can be de…
Characterization of exact one-query quantum algorithms (ii): for partial functions
Zekun Ye, Lvzhou Li
The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenti…
Characterization of exact one-query quantum algorithms
Weijiang Chen, Zekun Ye, Lvzhou Li
The quantum query models is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa alg…
Query complexity of generalized Simon's problem
Zekun Ye, Yunqi Huang, Lvzhou Li +1
Simon's problem plays an important role in the history of quantum algorithms, as it inspired Shor to discover the celebrated quantum algorithm solving integer factorization in poly…
Quantum speedup for twin support vector machines
Zekun Ye, Lvzhou Li, Haozhen Situ +1
We devise new quantum algorithms that exponentially speeds up the training and prediction procedures of twin support vector machines (TSVM). To train TSVMs using quantum methods, w…
A Note on "Quantum Algorithm for Linear Systems of Equations"
Yong-Zhen Xu, Yifan Huang, Zekun Ye +1
Recently, an efficient quantum algorithm for linear systems of equations introduced by Harrow, Hassidim, and Lloyd, has received great concern from the academic community. However,…