Weight discrimination of boolean functions with quantum computation

Download

index.pdf

Date

2014

Author

Uyanık, Kıvanç

Metadata

Show full item record

Item Usage Stats

245
views

110
downloads

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.

Subject Keywords

Quantum theory., Quantum mechanics., Boolean functions., Quantum computation.

URI

http://etd.lib.metu.edu.tr/upload/12617033/index.pdf
https://hdl.handle.net/11511/23414

Collections

Graduate School of Natural and Applied Sciences, Thesis

Suggestions

OpenMETU
Core

Quantum systems and representation theorem Dosi, Anar (2013-09-01) In this paper we investigate quantum systems which are locally convex versions of abstract operator systems. Our approach is based on the duality theory for unital quantum cones. We prove the unital bipolar theorem and provide a representation theorem for a quantum system being represented as a quantum -system.
Discrete symmetries in quantum theory Taşdan, İsmail Ufuk; Pak, Namık Kemal; Department of Physics (2015) In this thesis, one of the most central problems of modern physics, namely the discrete symmetries, is discussed from various perspectives ranging from classical mechanics to relativistic quantum theory. The discrete symmetries, namely charge conjugation (C), parity (P), time reversal (T), which are connected by the so-called CPT Theorem are studied in detail. The anti-particles with a view to matter-anti-matter symmetry is also addressed and the anti-unitarity nature of the time reversal, as well as the CP...
Discrimination of quantum states under local operations and classical communication Güngör, Özenç; Turgut, Sadi; Department of Physics (2015) One dimensional molecular potentials are studied by solving the Schrödinger Equation for some well known potentials, such as the deformed Morse, Eckart and the Hua potentials. Parametric generalization of Hamiltonian Hierarchy is introduced. Nikiforov-Uvarov method and SUSYQM with Hamiltonian Hierarchy method is used in the calculations to get energy eigenvalues and the corresponding wave functions exactly.
Quantum decoherence and quantum state diffusion formalism Dumlu, Cesim Kadri; Turgut, Sadi; Department of Physics (2007) Foundational problems of quantum theory, regarding the appearance of classicality and the measurement problem are stated and their link to studies of open quantum systems is discussed. This study's main aim is to analyze the main approaches that are employed in the context of open quantum systems. The general form of Markovian master equations are derived by a constructive approach. The Quantum State Diffusion (QSD) formalism is stressed upon as an alternative method to the master equations. Using the Calde...
Bell-like inequalities in quantum information theory Seskir, Zeki Can; Turgut, Sadi; Department of Physics (2015) Bell and Bell-like inequalities are essentil tools for identifying and inspecting quantum entanglement, a key phenomenon in quantum information theory. As the development of Quantum Information Theory progresses more and more Bell-like inequalities are formulated. An investigation of these and further inequalities will be given in their correspondences to Bell's and Kochen-Specker theorems. Also Hardy's test will be studied and particular applications of it for bipartitre and tripartite systems are going to...

Citation Formats

K. Uyanık, “Weight discrimination of boolean functions with quantum computation,” Ph.D. - Doctoral Program, Middle East Technical University, 2014.