6533b7dbfe1ef96bd126fe70

RESEARCH PRODUCT

Quantum versus classical query complexity of relation

Alina Vasilieva

subject

Quantum sortTheoretical computer scienceQuantum phase estimation algorithmSimon's problemQuantum algorithmQuantum informationQuery optimizationComputer Science::DatabasesQuantum complexity theoryQuantum computerMathematics

description

This paper investigates the computability of mathematical relations in a quantum query model. The important task in complexity theory is to find examples with a large gap between classical and quantum algorithm complexity of the same computational problem. We present new results in quantum query algorithm design that allow achieving a large separation between classical and quantum query complexity of a specific relation. We demonstrate an example where quantum query algorithm for a finite relation needs more than two times fewer queries than the best possible classical analogue. We also show that relation can be extended to infinite family of relations with an input of general size N.

yearjournalcountryeditionlanguage
2011-07-012011 Seventh International Conference on Natural Computation
https://doi.org/10.1109/icnc.2011.6022357