Quantum Computation and Quantum Information
On the power
of a unique quantum witness
Rahul Jain, Iordanis Kerenidis, Miklos Santha, Shengyu Zhang
Manuscript, arXiv:0906.4425, 2009.
A Survey of
BQP-Completeness
Shengyu
Zhang
Invited book chapter, Handbook of Natural
Computing, Springer-Verlag, 2009.
On the power
of lower bound methods for quantum one-way communication complexity
Shengyu
Zhang
Manuscript, 2008.
New bounds
on classical and quantum one-way communication complexity
Rahul
Jain, Shengyu Zhang
Theoretical Computer Science, 410 (26), pp.
2463-2477, 2009.
Measuring energy of basis
states in translationally invariant nearest-neighbor interactions in qudit
chains is universal for quantum computing
Dominik
Janzing, Pawel Wocjan, Shengyu Zhang
New Journal of Physics,
(10) 093004, 2008.
Making classical honest verifier zero
knowledge protocols secure against quantum attacks
Sean Hallgren, Alexandra
Kolla, Pranab
Sen, Shengyu Zhang
Proceedings of the 35th International Colloquium on Automata, Languages and
Programming
(ICALP), pp. 592-603, 2008.
(Best paper award of track C.)
Any AND-OR
formula of size N can be evaluated in time N1/2+o(1) on a quantum
computer
Andris Ambainis, Andrew Childs, Ben
Reichardt, Robert
Spalek, Shengyu Zhang
Proceedings of
the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 363-372, 2007.
(Merge of independent results
by the first author and
by the rest authors.
Journal version invited to SIAM Journal on Computing, special issue
for FOCS'07.)
Several
natural BQP-complete problems
Pawel
Wocjan, Shengyu Zhang
Manuscript, quant-ph/0606179, 2006.
Tight bounds for randomized and quantum Local Search
Shengyu Zhang
SIAM Journal on Computing, Vol 39, No. 3,
pp 948-977, 2009.
A
preliminary version
appeared in Proceedings of the 38th ACM Symposium on
Theory of Computing (STOC), pp. 634-643, 2006.
The
quantum query complexity, the approximate degree and the total influence
Yaoyun Shi, Shengyu Zhang
Manuscript, 2005.
Promised and
distributed quantum search
Shengyu Zhang
Proceedings
of the 11th International Computing and Combinatorics Conference (COCOON),
pp. 430-439, 2005.
On the power of Ambainis lower
bounds
Shengyu
Zhang
Proceedings
of the 31st International Colloquium on Automata, Languages and Programming
(ICALP),
pp. 1238-1250, 2004.
Journal version invited to
Theoretical Computer Science (special issue for ICALP'04)
and appeared in 339(2-3), pp. 241-256, 2005.
Graph
properties and circular functions: how low can quantum query complexity go?
Xiaoming Sun, Andrew
Yao, Shengyu Zhang
Proceedings of
the19th Annual IEEE Conference on Computational Complexity (CCC), pp.
286-293, 2004.
Lower
bound on inconclusive probability of unambiguous discrimination
Yuan Feng,
Shengyu
Zhang, Runyao Duan,
Mingsheng Ying
Physical Review A, 66, 062313, December
2002.
Set discrimination of quantum states
Shengyu
Zhang, Mingsheng
Ying
Physical Review A, 65, 062322, June 2002.
Universal
and original-preserving quantum copying is impossible
Yuan
Feng, Shengyu Zhang, Xiaoming Sun,
Mingsheng Ying
Physics Letters
A, 297(1-2), pp. 1-3, 2002.
Mathematical
nature of and a family of lower bounds for the success probability of
unambiguous discrimination
Xiaoming Sun, Shengyu
Zhang, Yuan Feng, Mingsheng
Ying
Physical
Review A, 65, 044306, April 2002.
Probabilistic
cloning and deleting of quantum states
Yuan Feng,
Shengyu
Zhang, Mingsheng Ying
Physical
Review A, 65, 042324, April 2002.
Upper
bound for the success probability of unambiguous discrimination among quantum
states
Shengyu Zhang, Yuan
Feng,
Xiaoming Sun, Mingsheng
Ying
Physical Review
A, 64, 062103, November 2001.
Applied Algorithms
Combinatorial algorithms for nearest neighbors, near-duplicates and
small-world design
Yury Lifshits, Shengyu Zhang
Proceedings of the 20th Annual ACM-SIAM Symposium
on Discrete Algorithms (SODA), 318-326, 2009.
Information diffusion on a
circle
Xiaojie Gao, Kevin Ko, Shengyu Zhang
Manuscript, 2008.
Streaming
algorithms measured in terms of the computed quantity
Shengyu Zhang
Proceedings of the 11th International
Computing and Combinatorics Conference (COCOON), pp. 338-348, 2007.
Distributed
rate allocation for inelastic flows
Prashanth
Hande, Shengyu Zhang, Mung
Chiang
IEEE/ACM Transactions on Networking, vol. 15, no. 6, pp. 1240-1253, December 2007.
(Journal version of the
INFOCOM’05 paper below, but with significant additions beyond the conference version.)
Distributed
rate allocation for inelastic flows: optimization frameworks, optimality
conditions and optimal algorithms
Mung Chiang, Shengyu Zhang, Prashanth
Hande
Proceedings of the 23rd Annual
Joint Conference of the IEEE Computer and Communications Societies (INFOCOM),
pp. 2679-2690, 2005.
Complexity theory
Depth-Independent
Lower bounds on the Communication Complexity of Read-Once Boolean Formulas
Rahul
Jain, Hartmut Klauck, Shengyu Zhang
Manuscript, arXiv:0908.4453, 2009.
On
the tightness of the Buhrman-Cleve-Wigderson simulation
Shengyu Zhang
To appear in
Proceedings of the 20th International Symposium on Algorithms and
Computation (ISAAC), 2009.
How
many rounds can Random Selection handle to obtain general zero-knowledge
protocols?
Shengyu
Zhang
Information Processing Letters,
accepted.
The
communication complexity of the Hamming Distance problem
Wei Huang, Yaoyun Shi,
Shengyu Zhang, Yufan Zhu
Information
Processing Letters, 99(4), pp.
149-153, 2006.
On the average sensitivity of monotone Boolean functions
Shengyu Zhang
Manuscript, 2004.
Others
Research on
version backtracking in cooperative design
Xiang Cao, Shengyu
Zhang, Guoqin Zheng,
Jiaguang Sun
Proceedings of the
7th International Conference on Computer Aided Design and Computer Graphics, Volume 2, pp. 656-661, 2001.
Action reliability of
probabilistic transition systems
Shengyu Zhang,
Mingsheng
Ying
Manuscript,
2001.