IEEE Computer Society Annual Symposium on VLSI

FPGA-Based Circuit Model Emulation of Quantum Algorithms

Mahdi Aminian, Mehdi Saeedi, Morteza Saheb Zamani, Mehdi Sedighi

Quantum Design Automation Lab
Computer Engineering Department, Amirkabir University of Technology, Tehran, Iran
{mahdi_aminian, msaeedi, szamani, msedighi}@aut.ac.ir

Abstract Section 2, basic concepts are presented. Previous work

is reviewed in Section 3. The proposed method and the
It can be shown that if quantum algorithms run on experimental results are described in Section 4 and
quantum computers, their processing speeds improve Section 5, respectively and finally, Section 6 concludes
exponentially compared to their classical counterparts. the paper.
However, due to the lack of quantum computers circuit
model of quantum algorithms are currently simulated 2. Quantum computing
using classical computers to verify their
functionalities. On the other hand, software simulation 2.1. Basic concepts
cannot use the intrinsic parallelism of quantum
algorithm efficiently. To address the problem, in this While a classical bit is represented by an electrical
paper hardware emulation of quantum algorithms are voltage value or a wire current value, a quantum bit,
discussed. To emulate quantum algorithms using qubit in short, can take any linear combination of the
FPGAs, a new representation for quantum bits is two basic states |0〉 and |1〉 called a superposition state
emulated that improves the emulation of quantum [1]. In other words, the state of a qubit |ψ〉, can be
circuits considerably. This representation could be described by (1) where C1 and C2 are complex numbers
used in both distinct and entangle qubit states. and ||C1||2+||C2||2=1. On the other hand, the state of a
qubit can also be shown by a 2-dimentionl vector [C1
1. Introduction C2]T denoted as (2) [3].

It has been shown that quantum computing could ψ = C1 0 + C 2 1 (1)

improve the rate of advance in processing power at
least for several applications [1], [2]. In other words, 1 0 C 
ψ = C1   + C 2   =  1  (2)
there are several problems that cannot be executed on a 0 1 C 2 
classical Turing machine as efficiently as a quantum
Unlike the classical bits, it is not possible to find the
computer. As a result, quantum computing has
exact value of an unknown qubit using a measurement
received significant attentions recently.
operator [1]. In other words, while the state of a qubit
On the other hand, there are many challenges that
may be any linear combination of two possible basic
need to be solved to build a scalable quantum computer
[2], [3]. Due to the lack of an existing quantum states |0〉 and |1〉, upon measurement its state collapses
computer, simulating quantum algorithms on a to |0〉 or |1〉 with the probability of ||C1||2 and ||C2||2,
classical computer is widely used to verify the respectively [17].
functionalities of quantum algorithms [4], [5]. Based on the above notations, a quantum system of
However, software simulation cannot profit the size N can be constructed using the tensor product [1].
intrinsic parallelism of quantum algorithms The property of working on multiple input states
completely. On the other hand, using the parallel simultaneously leads to a significant parallelism in
nature of hardware architectures may be more suitable quantum algorithms and it is one of the major quantum
to efficiently emulate quantum algorithms. computation advantages.
In this paper, an efficient method is proposed to Furthermore, the state of a qubit may completely
emulate quantum algorithms using a classical FPGA. depend on the state of another qubit. This amazing
The rest of the paper is organized as follows. In property, known as entanglement, is one of the other

978-0-7695-3170-0/08 $25.00 © 2008 IEEE 399

DOI 10.1109/ISVLSI.2008.43
Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on May 06,2025 at 14:09:41 UTC from IEEE Xplore. Restrictions apply.
 benefits of quantum computation. While two qubits are 2.2.5. Hadamard (H, Figure 1-e). This 1-input gate is
entangled, its state cannot be expressed as tensor used to produce a superposition state. The QMatrix of
product of two distinct qubits [1]. this gate and the result state |ψ5〉 after applying H are
shown in (7).
2.2. Quantum gates ψ5 =
1
((C1 + C 2 ) 0 + (C1 − C 2 ) 1 ),
2 (7)
A quantum system which performs a specific 1 1 1 
operation on a selected set of qubits in a fixed period of UH =  
2 1 − 1
time is called a quantum gate. It can be shown that the
behavior of a quantum gate is always linear [6].
Therefore, a quantum gate can be represented by a 2.2.6. Phase-Shift (PS, Figure 1-f). The PS gate is a
unitary matrix, called QMatrix [12]. Previously, 1-input gate which changes the phase of vector |1〉 of
various quantum gates with different functionalities the input state. In other words, the result of applying
have been proposed [1], [2], [6], among them, the this gate on the input qubit |ψ〉 is |ψ6〉 as shown in (8).
following gates are used in this paper and defined as: 1 0 
ψ 6 = C 0 + e iϕ C 1 , U = (8)
1 2 PS 0 eiϕ 
 
2.2.1. X (Figure 1-a). X is a 1-qubit gate that performs
the NOT operation on the input qubit. In other words, 2.2.7. Rotate (R, Figure 1-g). The R gate is a special
the state |ψ〉 of (1) is changed to |ψ1〉 illustrated as (3). case of PS gate with a specific phase. The result of
The QMatrix of X, i.e. UX, is also shown in (3). applying it on the input qubit |ψ〉 and its QMatrix are
0 1  (3) shown in (9).
ψ =C 0 +C 1 , U = 
1 2 1 X 1 0 j
ψ 7 = C1 0 + e 2πi / 2 C 2 1 ,
(9)
2.2.2. Y (Figure 1-b). As another 1-qubit gate, 1 0 
UR =  j 
consider the gate Y which changes the state |ψ〉 to |ψ2〉 j 0 e 2πi /2 
shown in (4) with the QMatrix UY.
0 − i  (4) 2.2.8. Controlled-Rotate (CR, Figure 1-h). This is a
ψ = −iC 0 + iC 1 , U = 
2 2 1 Y  i 0 
2-input gate with two control and target qubits, where
the target is rotated if the control input is equal to 1.
2.2.3. Z (Figure 1-c). To invert the phase of the input This gate also causes the entanglement of its two
qubit |ψ〉, the Z gate with QMatrix UZ defined as (5) inputs. The QMatrix of this gate is shown in (10).
could be applied.
' ' 2πi / 2 j '
1 0  ψ = C C 00 + C C 01 + e C C 10 +
ψ 3 = C1 0 − C 2 1 , UZ =   (5) 8 1 1 1 2 2 1
0 − 1 (10)
2πi / 2 j '
e C C 11 ,
2 2
2.2.4. Controlled-NOT (CNOT, Figure 1-d). This is
a 2-input gate with two control and target qubits, where 1 0 0  0
the target is complemented if the control input is equal 0 1 0  0
U = 0 
to 1. This gate causes the entanglement of its two CR 0 1 0
j  j

inputs. As a result, the output of this gate cannot be 0
 0 0 e2πi / 2 
shown as two distinct qubits using the tensor product.
The QMatrix of this gate is shown in (6).
ψ Control = C1 0 + C 2 1 , ψ Target = C1' 0 + C 2' 1 Since each unitary 2n × 2n matrix can describe a
valid quantum gate of size n, it can be said that the
' ' ' '
(6) number of quantum gates are infinite [6]. However,
ψ = C C 00 + C C 01 + C C 11 + C C 10
4 1 1 1 2 2 1 2 2 only a finite set of gates is needed to implement
1 0 0 0 quantum algorithms where these gates comprise a
0 1 0 0 universal set of quantum gates [1]. The set of CNOT,
U =  H, and PS gates that are used in this paper is universal
CNOT
0 0 0 1
 set of quantum gates [1].
0 0 1 0 

400

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on May 06,2025 at 14:09:41 UTC from IEEE Xplore. Restrictions apply.
 (for example see [11]-[15]) that only consist of X, Y, Z,
and CNOT gates are simulated quickly with significant
decrease in the required resources.
Based on the required operations, the used library of
this paper is divided into two separated parts, where
the first one includes the gates H, PS, R, and CR, and
the second one contains the gates X, Y, Z, and CNOT.
For the sake of simplicity, these two sets are named
HRC and XYZC, respectively.
To represent complex coefficients of each qubit,
fixed-point numbers are represented as Figure 2. Since
each qubit has two complex coefficients, it can be
represented by four fixed-point numbers. In addition,
Figure 1. Symbols of quantum gates, (a) X, (b) Y, (c) the number of mantissa bits in Figure 2 can be
Z, (d) Controlled-NOT, (e) Hadamard, (f) Phase-Shift, increased to attain more emulation accuracy.
(g) Rotate, (h) Controlled-Rotate

3. Previous Work
Figure 2. Representation of fixed-point numbers
When qubits are entangled, the size of required
QMatrix is increased. As an example, for a system with 4.1. The HRC group
three entangled qubits, the size of a basic 2×2 H
QMatrix is changed to 23×23. Therefore, to implement Based on (7), H needs four multiplications and four
it on a classical computer, too many resources will be additions on fixed-point numbers. Similarly, the
needed. As a result, software simulation cannot be implementation of PS gate needs four multiplications
done efficiently due to exponential increase in the size and two additions. As R can be seen as a special case
of matrices [7]. of PS gate, the same number of resources should be
The authors of [7] used the circuit model of a assigned.
quantum algorithm to evaluate the functionality of a The two inputs CR gate rotating the target qubit if
circuit using FPGA. In this method, the complex the control line is equal to 1 produces an entanglement
numbers C1 and C2 in (1) are represented as fixed point state. When the entanglement occurs, more resources
numbers and the gates X, Z, CNOT, PS and H are are needed for simulating. For example, applying a 1-
implemented based on multiply and add operations and input H gate on three entangled qubits needs sixteen
several coefficient swapping. At each state, the gate multipliers and sixteen adders while applying this gate
outputs are saved using intermediate registers, while, it on one qubit needs four multipliers and four adders.
consumes too many registers to save.
In [8] DSP techniques are used to implement
quantum gates. In other words, gates that can be
implemented by a coefficient swapping operation are
emulated based on the Network of Butterflies model
Figure 3. Added bits to qubit coefficient for the XYZC
[8]. However, only a small set of gates including gate family
classical reversible gates can be implemented by this
method.
4.2. The XYZC group
In [9], [10], a hardware emulation technique was
proposed to implement a limited group of quantum
The gates of the XYZC group are implemented using
algorithms. In other words, emulation of the algorithms
three extra bits added to each qubit coefficient as
containing an H in the first stage and a CNOT in the
shown in Figure 3. This method causes that needed
second stage is the main topic of this paper.
registers to save intermediate coefficients become zero.
Therefore, these gates are efficiently manipulated as
4. Proposed method shown in Figure 4.
The goal of this paper is to relax gate type limitation
of previous emulation methods. By adding several new
bits to stored coefficients, a lot of quantum algorithms

401

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on May 06,2025 at 14:09:41 UTC from IEEE Xplore. Restrictions apply.
 As shown in the experimental results section, the
implementation of XYZC gates needs a few gates and
registers for both distinct and entangled qubits (Table
1). When a quantum circuit includes only X, Y, Z, and
CNOT gates, it is better to use entangled qubits from
the beginning, as the cost of distinct to entangled qubit
Figure 4. Implementation of X, Y, Z gates in the bit conversion is too high. In the next section, the
mode experimental results are shown.
However, in the case of CNOT gate, entangled
qubits are produced and additional bits should also be 6. Experimental results
considered as shown in Figure 5 where n is the number
of qubits. In the case of entanglement, the number of The proposed emulation method was implemented
additional bits will be too small. CNOT gate is using VHDL and evaluated for various library gates in
implemented by XORing the control and target bits for both distinct and entangled qubits.
this case. Table 1 depicts logic cell usage for the
implementation of each gate with two different
mantissa sizes. In addition, the proposed method was
compared with another hardware emulation method
proposed in [7]. ALTERA STRATIX EP1S80B956C6
[19] device was chosen for all of the experiments. For
Figure 5. Added bits to entangled qubits coefficients
CNOT gate, a two entangled qubits circuit was
attempted. Furthermore, the number of intermediate
This strategy is used when a given circuit is built
registers was computed for the method of [7]. In this
from only XYZC group gates. When both XYZC and
table, the percentage of LC usage improvement is
HRC gates are used, the applied policy is different and
denoted as Imp.
gate operations are implemented by a coefficient
swapping operator using intermediate registers as
Table 1. LC usage on STRATIX EP1S80B956C6
stated below: device
1) The gate X swaps the complex coefficients C1 and
C2. Therefore, it needs four registers. Mantissa = 8 bits Mantissa = 16 bits
2) The gate Z is implemented by multiplying -1 to the
complex coefficient C2. Gate
Proposed Imp Proposed Imp
3) For the gate Y, in addition to swapping coefficients, method
[7]
% method
[7]
%
multiplying the complex number i (or –i) is also
required. It is implemented by swapping the real
H 398 704 43 808 1284 37
and imaginary parts of the coefficients and
inverting the sign bit if needed. PS 200 386 48 405 708 43
4) The outputs of a CNOT gate are produced in an
entangled format as shown in Figure 6. To emulate X 2 40 95 2 72 97
it, the tensor product of distinct qubits should be
used to create several new entangled qubits where Y 6 - - 6 - -
four complex number multiplications are needed.
Furthermore, applying the CNOT gate on two Z 2 40 95 2 72 97
entangled qubits needs swapping the coefficients
C2C1’ and C2C2’. CNOT 4 120 96 4 375 99

ψ 1 = a1 0 + a2 1
As shown in Table 1, the improvements for some
ψ 2 = b1 0 + b2 1 circuits (e.g. Z gate), are much more than others (e.g. H
gate), this is because the emulation method for circuits
ψ 1ψ 2 = a1b1 00 + a1b2 01 + a 2 b1 10 + a 2 b2 11 with XYZC gates are more efficient.
Figure 6. Producing two entangled qubits using the The Quantum Fourier Transform (QFT) is an
tensor product important quantum algorithm with great applications in

402

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on May 06,2025 at 14:09:41 UTC from IEEE Xplore. Restrictions apply.
 phase estimation, order-finding and factoring Table 4. Specification of benchmark circuits
algorithms [1], [7], [16]. An N-qubit QFT circuit is
shown in Figure 7. This circuit is constructed using H # of # of # of # of # of # of
Circuit Qubits Gates NOT CNOT C2NOT C3NOT
and CR gates where the CR gate produces an entangled
state.
Full Adder 5 6 0 3 3 0

3_17tc 3 6 1 3 2 0

graycode6 6 5 0 5 0 0

Ham3tc 3 5 0 4 1 0
Hwb4-11-
4 11 0 8 3 0
23
Mod5adder-
6 15 6 0 5 4
15

Figure 7. Circuit model of an N-qubit QFT algorithm rd32 4 4 0 2 2 0

xor5d1 5 4 0 4 0 0

The synthesis results for a 3-input QFT algorithm is Mod5d1 5 8 0 4 4 0

shown in Table 2. In addition, the run time of both the
proposed method and a software simulator, called Rd53d2 8 12 0 4 8 0
Libquantum [18], is depicted in Table 3.
Table 5. LC usage for synthesis of benchmarks [20]
Table 2. Synthesis result of QFT algorithm Proposed Method [7]
Circui
M
Clock Frequency (MHz) t E T E T
LC LC LC
Mantissa (ns) (min) (ns) (min)
Usage Proposed
[7]
method Full 8 128 6.43 1 3840 15 4.5
8 3905 137.9 - Adder 16 128 6.43 1.5 6912 15 12.5

16 8197 131.3 82.1 8 24 4.48 0.5 960 15 1

3_17tc
16 24 4.48 0.5 1728 15 1.25

grayco 8 320 4.45 4 6400 12.5 10

Table 3. The comparison of software simulation and de6 16 320 4.45 9.25 11520 12.5 25
the proposed hardware emulation method for the 3-
ham3t 8 24 4.48 0.25 800 12.5 0.75
input QFT algorithm
c 16 24 4.48 0.25 1440 12.5 1
Run Time (Seconds)
Mantissa hwb4- 8 64 4.51 0.5 3520 27.5 1.5
(bits) Libquantum Proposed 11-23 16 64 4.51 0.75 6336 27.5 3.5
[17] Method
mod5 8 576 11.1 10.5 19200 37.5 30.5
adder-
16 40 × 10-6 46 × 10-9 16 576 11.1 27 34560 37.5 70.5
15
8 48 4.48 0.5 1280 10 1
rd32
16 48 4.48 0.5 2304 10 1.25
To further analyze the proposed emulation method, xor5d 8 128 5.51 1 2560 10 3.5
several other quantum circuits, i.e. quantum full adder 1 16 128 5.51 1.75 4608 10 8
[2] and some of the available benchmarks [20] were
mod5 8 224 10.4 1.5 5120 20 4.5
synthesized. The characteristics of the circuits are
d1 16 224 10.4 3.75 9216 20 19
illustrated in Table 4 and the synthesis results are
depicted in Table 5. 8 3072 7.5 182 U - >240
rd53d
2
16 3072 7.5 210 U - >240

403

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on May 06,2025 at 14:09:41 UTC from IEEE Xplore. Restrictions apply.
 Note that the synthesis results of [7] were not [9] M. Fujishima, K. Saito, M. Onouchi, H. Hoh, “High-
reported in the paper. To make it possible to compare Speed Processor for Quantum-Computing Emulation and its
the results of the proposed method with [7], we Applications”, International Symposium on Circuits and
implemented it and its results are compared to those of Systems, Volume 4, 2003, PP. IV-884 - IV-887.
[10] M. Fujishima, “FPGA-Based High-Speed Emulator of
our method in Table 5. The following notations were
Quantum Computing”, International Conference on Field-
used for this table: M as mantissa, E as required Programmable Technology, 2003, PP. 21 - 26.
emulation time in nanosecond, T as total synthesis time [11] K. Iwama, Y. Kambayashi, S. Yamashita,
in minutes and U to mean that it is impossible to fit a “Transformation Rules for Designing CNOT-Based Quantum
circuit in the selected device. As shown in Table 5, it Circuits”, Design Automation Conference, 2002, PP. 419-
can be verified that the required LCs as well as the 424.
emulation time for the proposed method are fewer than [12] M. Saeedi, M. Sedighi, M. Saheb Zamani, “A New
the method of [7], significantly. Methodology for Quantum Circuit Synthesis: CNOT-Based
Circuits as an Example”, International Workshop on Logic
Synthesis, 2007.
7. Conclusion [13] A. Younes, J. Miller, “Automated method for building
CNOT based quantum circuits for Boolean functions”, Los
In this paper, an efficient quantum circuit emulation Alamos physics preprint archive, quant-ph/0304099, 2003.
technique is proposed. As this method uses the [14] A. Younes, J. Miller, “Representation of Boolean
parallelism of quantum algorithms, it offers more Quantum Circuits as Reed-Muller Expansions”, Los Alamos
efficiency than software simulation. Compared with Physics preprint archive, quant-ph/0305134, 2003.
the available hardware emulation methods, the [15] M. Saeedi, M. Sedighi, M. Saheb Zamani, “A Novel
Synthesis Algorithm for Reversible Circuits”, International
proposed technique uses fewer logic cells for the
Conference on Computer-Aided Design, 2007, PP. 65-68.
implementation of various quantum algorithms. In [16] Z. Zilic, K. Radecka, “The Role of Super-fast
other words, by using a novel representation schema Transforms in Speeding up Quantum Computations”,
and simulating the behaviors of various quantum gates International Symposium on Multiple-Valued Logic, 2002,
using simple logical gates, a great improvement is PP. 129 - 135.
obtained. Due to the efficiency of the proposed [17] Wikipedia, “Quantum Computer”, July 2007.
method, the simulation of large size quantum [18] “LibQuantum”, Online Quantum Library
algorithms is also possible. Documentation, Available: http://www.enyo.de/libquantum/
[19] http://www.altera.com/
[20] D. Maslov, “Reversible Logic Synthesis Benchmarks”,
10. References Available: http://webhome.cs.uvic.ca/~dmaslov/

[1] M. A. Nielsen, I.L. Chuang, Quantum Computation and

Quantum Information, Cambridge University Press, Wiley
Publishing, 2000.
[2] D. C. Marinescu, G. M. Marinescu, Approaching
Quantum Computing, Prentice Hall, 2005.
[3] S. Imre, F. Balazs, Quantum Computing and
communications: An Engineering Approach, John Wiley
Publishing, 2005.
[4] I. G. Karafyllidis, “Quantum Computer Simulator Based
on the Circuit Model of Quantum Computation”, IEEE
Transactions on Circuits and Systems, Volume 52, 2005, PP.
1590 – 1596.
[5] G. F. Viamontes, I. L. Markov, J. P. Hayes, “Improving
Gate-Level Simulation of Quantum Circuits”, Quantum
Information Processing, Volume 2(5), 2003, PP. 347-380.
[6] A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVincenzo,
N. Margolus, P. Schor, T. Sleator, J. Smolin, H. Weinfurter,
“Elementary Gates for Quantum Computation”, Physical
Rev, No. 52, 1995, pp. 3457-3467.
[7] A. U. Khalid, Z. Zilic, K. Radecka, “FPGA Emulation of
Quantum Circuits”, International Conference on Computer
Design, 2004, PP. 310- 315.
[8] G. Negovetic, M. Perkowski, M. Lukac, A. Buller,
“Evolving Quantum Circuits and an FPGA-Based Quantum
Computing Emulator”, International Workshop on Boolean
Problems, 2002.

404

Authorized licensed use limited to: Universidad Federal de Pernambuco. Downloaded on May 06,2025 at 14:09:41 UTC from IEEE Xplore. Restrictions apply.