Abstract
The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis’ technique for these problems.
Research supported by Grant No.01.0354 from the Latvian Council of Science
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ambainis, A.: Quantum Lower Bounds by Quantum Arguments. Journal of Computer and System Sciences 64, 750–767 (2002)
Ambainis, A.: Personal communication (2003)
Bennett, C.H., Bernstein, E., Brassard, G., Vazirani, U.V.: Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing 26, 1510–1523 (1997)
Buhrman, H., de Wolf, R.: Complexity Measures and Decision Tree Complexity: A Survey. Theoretical Computer Science 288(1), 21–43 (2002)
Freivalds, R., Winter, A.: Quantum Finite State Transducers. In: Pacholski, L., Ružička, P. (eds.) SOFSEM 2001. LNCS, vol. 2234, pp. 233–242. Springer, Heidelberg (2001)
Grover, L.: A Fast Quantum Mechanical Algorithm for Database Search. In: Proceedings of the 28th ACM symposium on Theory of Computing, pp. 212–219 (1996)
Gruska, J.: Quantum Computing. McGraw-Hill, New York (1999)
Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000a)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Berzina, A., Dubrovsky, A., Freivalds, R., Lace, L., Scegulnaja, O. (2004). Quantum Query Complexity for Some Graph Problems. In: Van Emde Boas, P., Pokorný, J., Bieliková, M., Štuller, J. (eds) SOFSEM 2004: Theory and Practice of Computer Science. SOFSEM 2004. Lecture Notes in Computer Science, vol 2932. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24618-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-24618-3_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20779-5
Online ISBN: 978-3-540-24618-3
eBook Packages: Springer Book Archive