“Computer graphics for quantum computation” by Zarina and Freivalds
Conference:
Type(s):
Title:
- Computer graphics for quantum computation
Presenter(s)/Author(s):
Abstract:
The center of interests in quantum computation [Nielsen and Chuang 2000] is gradually moving towards small computational devices. The decision tree complexity of f is related to representing Boolean functions by polynomials. Let D(f) be the deterministic decision tree complexity and QE(f) be the exact quantum decision tree complexity. For any Boolean function f, there is a unique multilinear polynomial p such that p(x1, . . ., xn) = f(x1, . . ., xn). deg(f), the exact degree of a function f is the degree of corresponding polynomial p. We have D(f) ≥ deg(f) and QE(f) ≥ deg(f) 2. Our main goal is to construct Boolean functions for which quantum decision tree complexity QE(f) is much lower than the deterministic decision tree complexity D(f). Inevitably such a function must have small deg(f).
References:
1. {Kalnins et al. 2005} Kalnins, A., Barzdins, J., Celms, E. Model Transformation Language MOLA. Lecture Notes in Computer Science, vol. 3599, 2005, pp. 62–76.
2. Nielsen and Chuang 2000} Nielsen, M., Chuang, I. Quantum Computation and Quantum Information. Cambridge University Press, New York, 2000, 700 pp.
