[5] Mohammadi M and Eshghi M 2009 On figures of merit in reversible and quantum logic designs Quantum Inf. Process. 8 297–318
[6] Monroe C, Meekhof D M, King B E, Itano W M and Wineland D J 1995 Demonstration of a fundamental quantum logic gate Phys. Rev. Lett. 75 4714
[7] Nielsen M A and Chuang I L 2000 Quantum Computation and Quantum Information 10th edn (Leiden: Cambridge University Press)
[8] Shende V V, Prasad A K, Markov I L and Hayes J P 2003 Synthesis of reversible logic circuits IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 22 710–22
[9] Toffoli T 1980 Reversible computing International Colloquium on Automata, Languages, and Programming (Berlin: Springer) pp 632–44
[10] Zhou R-G, Li Y-C and Zhang M-Q 2014 Novel designs for fault tolerant reversible binary coded decimal adders Int. J. Electron. 101 1336–56
IOP Publishing
Quantum Computing
A pathway to quantum logic design
Hafiz Md Hasan Babu
Chapter 3
The quantum bit string comparator
The quantum bit string comparator enables the implementation of a quantum algorithm using conditional statements, a fundamental structure for designing algorithms. This widens the number of applications where quantum algorithms can be used and at the same time it brings quantum programmers close to some of the successful techniques used in classical computation based on comparisons. For example, constructing a database composed of only prime numbers is possible using the quantum bit string comparator.
3.1 Characteristics of a comparator
A comparator, as suggested by the name, compares a signal on one input of an op-amp, as shown in figure 3.1, with a known voltage called the reference voltage on the other input. The comparator is nothing other than an open loop op-amp with two analog inputs (differential input) and one digital output (signal ended output). The op-amp has a very large gain when used in an open loop. Hence the output may be in the positive or negative saturation voltage depending upon which input is larger. An op-amp is perfectly suited to comparator applications because of its high input impedance and large open loop gain.
Figure 3.1. An open loop op-amp.
The important characteristics of a comparator are:
1 Speed of operation.
2 Accuracy.
3 Compatibility of output.
3.2 The magnitude comparator
A magnitude comparator is a logic circuit that first compares the sizes of A and B and then determines the result among A>B, A<B, and A = B. When the two numbers in the comparator circuit are two one-bit numbers, the result will be only one bit from 0 and 1. Thus the circuit is called a one-bit magnitude comparator, which is a basis of comparison of the two numbers of n bits. A quantum bit string comparator is designed for the quantum bit string comparator circuit. In this chapter two quantum states are identified by providing a comparison status, such as equality or larger or smaller, after performing a comparison between these states. In addition, this chapter shows that the quantum bit string comparator enables us to implement conditional statements in quantum computation, which is a basic structure for designing a comparison algorithm. However, the design requires a huge number of quantum gates, garbage outputs, and constant inputs. Moreover, the design does not show the area and power requirements of the circuit. A quantum comparator circuit is designed for a quantum comparator circuit using quantum dot cellular automata. The design requires a huge number of quantum gates and garbage outputs.
An ASIC implementation of a low power area efficient folded binary comparator circuit was invented in 2014. This comparator consists of a pre-computation unit and an encoder block. The basic principle is to group the binary inputs into digit sets. The digit sets are sent to the pre-computation unit starting from the most significant digit (MSD) to check for equality, and the computations in the pre-computation unit are stopped at the first digit set which produces a 1 as output. The corresponding digit set is then sent to the carry look-ahead (CLA) encoder block to find the greater of the two inputs. However, as this is an irreversible comparator circuit, this circuit has huge dynamic power dissipation.
3.3 The design of a quantum comparator
There are two important properties to define a quantum gate which are as follows.
Property 3.1. Each quantum gate has an unique unitary matrix. A complex square matrix U is unitary only if
U*U=UU*=I,
where I is the identity matrix and U* is the conjugate transpose of U.
Property 3.2. A quantum state is represented by a state vector in a Hilbert space over complex numbers.
The matrices for the controlled-E and controlled-E+ gates are
Mcontrolled‐E=−i/2−i/2−i/2i/2;Mcontrolled‐E+=i/2i/2i/2−i/2.
The conjugate transpose of Mcontrolled‐E is Mcontrolled‐E+ and vice versa. After multiplying Mcontrolled‐E and Mcontrolled‐E+, we obtain an identity matrix which is
Mcontrolled‐E×Mcontrolled‐E+=−i/2−i/2−i/2i/2×i/2i/2i/2−i/2=1001=I.
The controlled-E and controlled-E+ gates have a unique matrix which is unitary. Figures 3.2(a) and (b) show the diagrams of the controlled-E and controlled-E+ gates.
Figure 3.2. Controlled gate. (a) Controlled-E+ gate. (b) Controlled-E gate.
The matrices for the XN (MXN) gate and its conjugate transpose (MXN*) are
MXN=0100100000100001MXN*=0100100000100001.
After multiplying MXN and MXN*, we obtain an identity matrix which is
MXN×MXN*=0100100000100001×0100100000100001=1000010000100001=I.
Thus the XN gate has a unique matrix which is unitary. Figure 3.3 shows the diagram of the XN gate.
Figure 3.3. The XN gate.
Algorithm 3.1 describes the computational process for the designed method for the proof of the time complexity. The technique of comparison of the comparator has four basic steps. First, sort the two numbers and also calculate their middle bit position. Second, find Ex-OR of the middle bit position and decide based on that value whether to go to the left half or to the right half of the numbers. Third, repeat the second step after entering into the left or right half and also calculate Ex-OR of the other bits at the same time. Finally, take a decision if any value of Ex-OR is ∣1〉 as to which number is greater, otherwise carry out Ex-NOR to find whether they are equal or not.
Property