Facets of Quantum Computation { Practice and Theory

Abstract

Quantum computation has seen rapid development both in theory as well as hardware and implementation in the past three decades. Against this backdrop we study both the implementational and theoretical aspects of quantum computation. In Part I we approach the problem of e cient implementation of quantum algorithm. The exact requirement of CNOT and single qubit gates needed for optimal implementation in a given architecture is one of the central problems in this computational paradigm. Speci cally, we study preparation of Dicke states (jDn k i ) using concise realizations of partially de ned unitary transformations. We further optimize the state of the art deterministic Dicke state preparation circuit in terms of CNOT and single qubit gates. We explain theoretical ideas in reducing the gate counts and observe how these improvements are re ected in actual implementation of the circuits. To emphasize the advantages, we describe the circuit for preparing jD4 2i on the \ibmqx2" machine of the IBM QX service. Our approach shows that the error induced due to noise in the system is lesser in comparison to the existing works. We conclude by describing the CNOT map of the generic jDn k i preparation circuit and analyze di erent ways of distributing the CNOT gates in the circuit and its e ect on the induced error in the Noisy Intermediate Scale Quantum (NISQ) environment. In Part II we concentrate on the query complexity model of evaluating functions for unknown inputs in a setup where the value of the input variables can only be accessed by making query to an oracle. First we study the separation between the deterministic query complexity (D(f)) and exact quantum query complexity QE(f) of query friendly functions (QF). These are functions on n variables with minimum D(f) value. We observe that there is a non separable QF function f (D(f) = QE(f)) for all values of n. Additionally, for some values of n all QF functions are non- 6 separable. Finally we construct separable QF functions for some other values of n via the parity method, which is the most well known exact quantum query algorithm. We further show that for rest of the values of n no separation can be obtained through parity decision tree model. Next we look into obtaining separation between D(f) and QE(f) that is not reachable via any parity method (D(2) (f)). In this direction we study the algebraic normal form of Boolean (ANF) functions to obtain separation between D(f) and QE(f) beyond parity for classes of non-symmetric functions. We combine existing results on Fourier analysis along with novel exact quantum algorithmic techniques that we design to obtain a class of direct sum based functions of size

p 2 p n

functions for which we have QE(f) < D(2) (f) < D(f) for which we design optimal quantum algorithm. In fact our algorithms are more e cient than any possible general parity method, a model in which one can obtain parity of any number of variables in one query. To the best of our knowledge, this is the rst family of algorithms beyond generalized parity (and thus parity) for a large class of non-symmetric functions. Finally we use our novel ANF based algorithmic techniques to obtain a d5n 8 e-query exact quantum algorithm for a set of Maiorana-McFarland type bent functions of size 22 n4 functions. This is better than the best parity method we could obtain for these functions, which has a query complexity of d3n 4 e.