Quantum Computing and Communications: An Engineering Approach

5

Quantum Parallelism

Quantum parallelism is one of the major driving forces of quantum computing and can be referred to as a solid basis of most quantum-based algorithms alongside entanglement. This special kind of parallel computation allows solving classically complex problems such as searching an unstructured database or finding prime factors of large numbers while breaking ciphering protocols during an astonishing short period of time. In order to lay dawn the foundations of sophisticated quantum algorithms mathematical formulation of quantum parallelism (Section 5.1) with simple practical examples of Deutsch–Jozsa and Simon algorithms (Section 5.2 and 5.3) are provided within this chapter.

5.1 INTRODUCTION

Let us assume that we have an unknown function f(x) : {0, 1}ⁿ → {0, 1}¹. In order to determine the exact rules of its operation classically we have to substitute all the potential inputs x = 0, 1, … , 2ⁿ − 1, which requires either a large amount of evaluation of f sequentially or we need to buy N = 2ⁿ pieces of parallel switched elementary gates implementing f.

We try to exploit the special features of the quantum world to build a quantum gate which is able to perform this job in a single step. First we solve this problem for f(x) : {0, 1}¹ → {0, 1}¹, which will be followed by the generalization of the binary result to n.

When we consider the master equation of the CNOT gate (2.10) with control input and data input |D〉_IN = |0〉 i.e., we produce Bell pair , we can observe ...