排序方式: 共有22条查询结果,搜索用时 20 毫秒
1.
2.
3.
4.
5.
Andris Ambainis Kazuo Iwama Masaki Nakanishi Harumichi Nishimura Rudy Raymond Seiichiro Tani Shigeru Yamashita 《Computational Complexity》2016,25(4):723-735
This paper considers the quantum query complexity of almost all functions in the set \({\mathcal{F}}_{N,M}\) of \({N}\)-variable Boolean functions with on-set size \({M (1\le M \le 2^{N}/2)}\), where the on-set size is the number of inputs on which the function is true. The main result is that, for all functions in \({\mathcal{F}}_{N,M}\) except its polynomially small fraction, the quantum query complexity is \({ \Theta\left(\frac{\log{M}}{c + \log{N} - \log\log{M}} + \sqrt{N}\right)}\) for a constant \({c > 0}\). This is quite different from the quantum query complexity of the hardest function in \({\mathcal{F}}_{N,M}\): \({\Theta\left(\sqrt{N\frac{\log{M}}{c + \log{N} - \log\log{M}}} + \sqrt{N}\right)}\). In contrast, almost all functions in \({\mathcal{F}}_{N,M}\) have the same randomized query complexity \({\Theta(N)}\) as the hardest one, up to a constant factor. 相似文献
6.
In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automaton operating in realtime mode, whereas the size of the corresponding classical automata grows without bound. 相似文献
7.
We study the classic binary search problem, with a delay between query and answer. For all constant delays, we give matching upper and lower bounds on the number of queries. 相似文献
8.
9.
We give a new version of the adversary method for proving lower bounds on quantum query algorithms. The new method is based
on analyzing the eigenspace structure of the problem at hand. We use it to prove a new and optimal strong direct product theorem
for 2-sided error quantum algorithms computing k independent instances of a symmetric Boolean function: if the algorithm uses significantly less than k times the number of queries needed for one instance of the function, then its success probability is exponentially small
in k. We also use the polynomial method to prove a direct product theorem for 1-sided error algorithms for k threshold functions with a stronger bound on the success probability. Finally, we present a quantum algorithm for evaluating
solutions to systems of linear inequalities, and use our direct product theorems to show that the time-space tradeoff of this
algorithm is close to optimal.
A. Ambainis supported by University of Latvia research project Y2-ZP01-100. This work conducted while at University of Waterloo,
supported by NSERC, ARO, MITACS, CIFAR, CFI and IQC University Professorship. R. Špalek supported by NSF Grant CCF-0524837
and ARO Grant DAAD 19-03-1-0082. Work conducted while at CWI and the University of Amsterdam, supported by the European Commission
under projects RESQ (IST-2001-37559) and QAP (IST-015848). R. de Wolf supported by a Veni grant from the Netherlands Organization
for Scientific Research (NWO) and partially supported by the EU projects RESQ and QAP. 相似文献
10.