Weight discrimination of boolean functions with quantum computation

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Fen Edebiyat Fakültesi, Fizik Bölümü, Türkiye

Tezin Onay Tarihi: 2014

Öğrenci: KIVANÇ UYANIK

Danışman: SADİ TURGUT

Özet:

In this thesis, we investigate solvability of the weight decision problem of two Boolean functions by quantum computation. In particular, we study this problem first from a general quantum operator discrimination perspective and second from a direct algorithmic viewpoint. As quantum operator discrimination approach is concerned, we give two different formulations for two different cases. In one, the unitary transformations that correspond to the function evaluation are applied in a parallel fashion and in the other, they are applied only sequentially. Since the parallel case can always be simulated with a serial architecture, we put more emphasis on the serial approach and present a superior result in the serial setting. Specifically we show that any protocol with a serial application of p function evaluations interspersed with p − 1 generic unitary operators in between can be uniquely mapped to a density matrix acting on some other Hilbert space. In the direct approach, we generalize Grover’s iteration in such a way that it can be run deterministically for the discrimination of Boolean functions. We show that sure-success weight distinguishability problem of two Boolean functions using a certain number of evaluations can be reduced to the problem of determining whether a point lies inside the convex hull of a curve. This convex analysis problem is further translated into a system of algebraic equations of a single variable. These equations are solved analytically for the case of single and two evaluations. For more evaluations numerical methods are utilized.