Читать книгу Quantum Computing - Hafiz Md. Hasan Babu - Страница 29

Оглавление

IOP Publishing

Quantum Computing

A pathway to quantum logic design

Hafiz Md Hasan Babu

Chapter 5

The quantum multiplexer and demultiplexer

In large-scale computing systems, it is necessary for a single line to carry two or more signals. One signal can be placed on one line at a time. However, the device which will allow us to select and place the signal we choose on a common line, is called a multiplexer (MUX). The purpose of a MUX is to select the input of any n inputs and feed that to one output line. The function of a demultiplexer (DEMUX) is the opposite to the function of the MUX.

5.1 The quantum multiplexer

This section presents the design of the quantum multiplexer. The multiplexer causes the transmission of a large number of information units over a smaller number of channels. Architecturally a digital multiplexer is a logic circuit that puts one of several inputs to a single output. A set of selected inputs controls the inputs. Generally a multiplexer has m inputs and n selected inputs where m=2n.

5.1.1 The quantum 2-to-1 multiplexer

A 2-to-1 multiplexer is the smallest unit of architecture of a quantum multiplexer. The characteristic function of a multiplexer is s0′I0+s0I1. A quantum Fredkin gate, as shown in figures 5.1(a) and (b), can be used as a 2-to-1 quantum multiplexer as it can map the characteristic function of a multiplexer.

Figure 5.1. The quantum Fredkin gate. (a) Quantum circuit of a quantum Fredkin gate. (b) Symbol of a quantum Fredkin gate.

Let I₀ and I₁ be the inputs and S₀ be the selected input of a 2-to-1 multiplexer. When S0=0, then input I0 transmits to the output Y and when S0=1, then input I1 transmits to the output Y. Figure 5.2 shows the architecture of a quantum 2-to-1 multiplexer using a quantum Fredkin gate. The quantum cost and delay of this quantum 2-to-1 multiplexer are 5 and 5Δ, respectively. Moreover, the number of garbage outputs is two.

Figure 5.2. The quantum Fredkin gate as a quantum 2-to-1 multiplexer.

5.1.2 The quantum 4-to-1 multiplexer

The quantum 4-to-1 multiplexer has four inputs, two select lines, and one output. Figure 5.3 illustrates the design of a quantum 4-to-1 multiplexer, where I0, I1, I2, and I3 are the inputs, and S0 and S1 are the select lines. The bit combination of select lines controls the function of a 4-to-1 multiplexer, as presented in table 5.1. Three quantum Fredkin gates are used in this design. Thus the quantum cost of the quantum 4-to-1 multiplexer is 15 and the delay is 15Δ in the logic circuits, respectively; whereas the number of garbage outputs is five.

Figure 5.3. The quantum 4-to-1 multiplexer.

Table 5.1. Function of S0 and S1 select lines.

S ₀	S ₁	Output(O)
0	0	I ₀
0	1	I ₁
1	0	I ₂
1	1	I ₃

5.1.3 The quantum 2n-to-1 multiplexer

Figure 5.4 shows the design of a quantum 8-to-1 multiplexer. As the consequence of the design of quantum multiplexers, a 2n-to-1 multiplexer can be constructed using two 2n−1-to-1 quantum multiplexers and one 2-to-1 quantum multiplexer. Figure 5.5 presents the 2n-to-1 multiplexer, and the properties of the 2n-to-1 quantum multiplexer are given in property 5.1.

Figure 5.4. The quantum 8-to-1 multiplexer.

Figure 5.5. Block diagram of 2n-to-1 multiplexers.

Property 5.1. A quantum 2ⁿ-to-1 multiplexer can be designed with a 2n−1 gate which produces 2n+n−1 garbage outputs. It also requires a 5(2n−1) quantum cost and a delay of 5(2n−1)Δ, where n denotes the number of selection lines and Δ denotes the unit delay.

5.2 The quantum demultiplexer

This section presents the design of the quantum demultiplexer. A demultiplexer (or DEMUX) is a device that takes a single input line and routes it to one of several digital output lines. A demultiplexer of 2ⁿ outputs has n select lines which are used to select the output line to which to send the input. A demultiplexer is also called a data distributor. The demultiplexer can be used to implement general purpose logic. By setting the input to true, the DEMUX behaves as a decoder. The reverse of a multiplexer is the demultiplexer.

5.2.1 The quantum 1-to-2 demultiplexer

A 1-to-2 demultiplexer is the smallest unit of the architecture of a quantum demultiplexer. The characteristic function of a 1-to-2 demultiplexer is s0′D s0D on the different output line, as shown in table 5.2. A quantum Fredkin gate can be used as a 1-to-2 quantum demultiplexer as it can map the characteristic functions of a demultiplexer.

Table 5.2. Truth table of a 1-to-2 demultiplexer.

S	Y ₁	Y ₀
0	0	D
1	D	0

Let, D be the inputs and S0 the select input of a 1-to-2 demultiplexer. When S0=0, then D input is transmitted to the second output Y0 and when S0=1, then the D input is transmitted to the third output Y1. Figure 5.6 shows the architecture of a quantum 1-to-2 demultiplexer using a quantum Fredkin gate. The quantum cost and delay of this quantum 1-to-2 demultiplexer are 5 and 5Δ,respectively. Moreover, the number of garbage outputs is one.

Figure 5.6. The quantum Fredkin gate as a quantum 1-to-2 demultiplexer.

5.2.2 The quantum 1-to-4 demultiplexer

The quantum 1-to-4 demultiplexer has two select lines, one data input, and four outputs. Figure 5.7 shows the design of a quantum 1-to-4 demultiplexer where Y0, Y1, Y2, and Y3 are the outputs, and S0 and S1 are the select lines. The bit combination of select lines controls the function of the 1-to-4 demultiplexer, as shown in table 5.3. Three quantum Fredkin gates are used in this design. Thus the quantum cost of the quantum 1-to-4 demultiplexer is 15 and the delay of the quantum 1-to-4 demultiplexer is 15Δ, while the number of garbage outputs is two.

Figure 5.7. The quantum 1-to-4 demultiplexer.

Table 5.3. The truth table of a 1-to-4 demultiplexer.

S ₁	S ₀	Y ₃	Y ₂	Y ₁	Y ₀
0	0	0	0	0	D
0	1	0	0	D	0
1	0	0	D	0	0
1	1	D	0	0	0

5.2.3 The quantum 1-to-2ⁿ demultiplexer

Figure 5.8 shows the design of a quantum 1-to-8 demultiplexer. As a consequence of the design of the quantum demultiplexer, a 1-to-2ⁿ quantum demultiplexer can be constructed using a 1-to-2ⁿ⁻¹ quantum demultiplexer and 2n−1 quantum Fredkin gates, which is shown in figure 5.9. The properties of the 1-to-2ⁿ quantum demultiplexer are given in property 5.2.

Figure 5.8. The quantum 1-to-8 demultiplexer.

Figure 5.9. Block diagram of a 1-to-2ⁿ demultiplexer.

Property 5.2. A quantum 1-to-2ⁿ demultiplexer can be designed with 2n−1 gates which produce n garbage outputs. It also requires a 5(2n−1) quantum cost and a delay of 5(2n−1)Δ, where n denotes the number of selection inputs and Δ denotes the unit delay.

5.3 Summary

In this chapter the quantum multiplexer (MUX) and demultiplexer (DEMUC) are presented and explained with the quantum circuit representation. In the multiplexer section, a 2-to-1 MUX, 4-to-1 MUX, and 8-to-1 MUX are described and generalized to the 2n-to-1 multiplexer. In the demultiplexer section, a 1-to-2 DEMUX, 1-to-4 DEMUX, and 1-to-8 DEMUX are described and generalized to the 1-to-2n demultiplexer. Moreover, the quantum cost and delay of the multiplexers and demultiplexers are provided.