93 citations · 93 across the 2 of their papers we have counts for
5 papers
Distributed construction of quantum fingerprints
Andris Ambainis, Yaoyun Shi
Quantum fingerprints are useful quantum encodings introduced by Buhrman, Cleve, Watrous, and de Wolf (Physical Review Letters, Volume 87, Number 16, Article 167902, 2001; quant-ph/…
Both Toffoli and Controlled-NOT need little help to do universal quantum computation
Yaoyun Shi
What additional gates are needed for a set of classical universal gates to do universal quantum computation? We answer this question by proving that any single-qubit real gate suff…
Quantum lower bound for sorting
Yaoyun Shi
We prove that Ω(n log(n)) comparisons are necessary for any quantum algorithm that sorts n numbers with high success probability and uses only comparisons. If no error is allowed,…
Entropy lower bounds of quantum decision tree complexity
Yaoyun Shi
We prove a general lower bound of quantum decision tree complexity in terms of some entropy notion. We regard the computation as a communication process in which the oracle and the…
Lower bounds of quantum black-box complexity and degree of approximation polynomials by influence of Boolean variables
Yaoyun Shi
We prove that, to compute a Boolean function on variables with error probability , any quantum black-box algorithm has to query at least $\frac{1 - 2\sqrtε}{2} ρ_f N = \…