Term Papers MSCS
Click here to download
Capabilities and Limitations of Quantum Computers
Umar Farooq
Virtual University Pakistan
Abstract—Computers are evolving and growing for the last half a
century. They are becoming smaller, faster and powerful but this
growth has a limit. A new research has begun which will result in
an entirely new kind of computer based on the Quantum physics
rules. The quantum computer working on the Quantum physics
rules will be able to break the security codes on which our
modern computer infrastructure is running. The Quantum
computers can solve many problems which are not solvable by
the current computer systems. The large scale production of the
quantum computers is near, which will result in many
opportunities and every field of life will be affected.
Keywords— Quantum Computers, Qubit, Capabilities and
limitations, Computation, Complexity
I. INTRODUCTION
This is a long debate that what a quantum computer can do
and what they can’t. Quantum computers can simulate the
details of biological molecules, can work on intra galaxy
research, and can do whatever an ordinary computer can’t. So
this type of computer will become an important part of future
progress in chemistry, physics, mathematics and engineering.
Moreover the quantum computers will open new era of
research, development and progress. Experts also see the
quantum computers as threat because the computers of this
magnitude will break all the cipher codes which are working
in our ecommerce and computer systems.
Quantum computer works differently from the traditional
computers. The traditional computers can compute only one
transaction at a time, it is their speed by which they compute,
they seem doing multiple transactions. On the other hand the
quantum computers can perform multiple transactions at a
time with the speeds more than traditional computers
The fundamental building block of a quantum computer is
Qubit as shown in the diagram.
Fig1. The Bloch sphere is an illustration of a Qubit, the
basic building block of quantum computers. [16]
Qubits are different from the bits and can hold much more
information than the later. An ordinary bit can compute or
store 0 or 1 but a Qubit can work in between the values of 0
and 1.
Fig: 2 Quantum bit
Qubits are made up of two things first is the controlled
particles and second one is the means of control.
Fig: 3 Qubits [16]
The following table will show the comparison between the
classical computing and quantum computing.
TABLE I
COMPARISON OF TRADITIONAL AND QUANTUM COMPUTING
Comparison
Description Classical Quantum Computing Comuting
1 Information
storage and
representation
0 or 1 Qubit
2 Calculation
method
Using bits and logc
gates
Using states of
atoms
3 Delivery of
information
Information can be
copied without
distributing.
Information cannot
be copied or read
without
distributing
4 Behaviour of
information
One single direction On many
directions , like
multiple waves
5 Noise
Tolerance
Noisy channel can be
used to deliver the
information.
Noiseless channel
is required to
deliver the
information.
6 Security Hacker can break
into communication
Due to high
security alarm will
be raised.
7 Computation
Cost
Directly proportional
to the computation.
Inversely
proportional to
computation.
.
II. RELATED WORK
A Large 3-Dimensional cluster lattice is used as resource
for quantum computer information processing and it is also
used in mainframe computers. The idea can lead to a
construction of 7.5 billion photonic chips Quantum Computer.
[1]
The computer models which are motivated by physics have
both physical as well as computational interpretation and it
relates both of the systems. [2] Quantum mechanics represent
most of our understanding related to microscopic physical
phenomena and the operations of a computer should also be in
form of quantum mechanics. [3]
Quantum computing is still evolving and no one knows
when its requirements will be met, weather some tradeoffs
will be made or research on entirely new path will begun. [4]
It is proposed that how explicit microscopically models of
quantum computer register can be constructed, and sphere
models bonded with the first and second kind can be used to
represent quantum register. [17]
Figure: 4 Shows a Quantum Charged Coupled Device
(QCCD) [4]
Ion traps can be used as the building block of quantum
computers. The basic implementation of the system is
demonstrated but there are many problems to make the system
scalable to large QBITS. [4]
Figure: 5 Configuration of static and radio frequencies for
QCCD. [4]
III. HISTORY OF QUANTUM COMPUTING
The most advanced quantum computers till 2007 have yet
managed more than 16 QBITS, which means that a useful
quantum computer is far away. Quantum computers and the
quantum theory have made some advancement in recent years. In 1998 Los Alamos and MIT researchers tried to use a
single Qubit in three nuclear spins in each alanine molecules
in liquid form.
In 2000 March, Los Alamos National Laboratory scientists
announced that they have succeeded to develop a 7-qubit
quantum computer with a single drop of liquid.
In 2001 Scientists from IBM and Stanford University
successfully experienced Shor's Algorithm on a quantum
computer. This Algorithm is used for finding the prime factors
of numbers. They used a 7-qubit computer to calculate the
factors of 15. The computer correctly calculated that the prime
factors were 3 and 5.
In 2005 Quantum Optics and Quantum Information
Institute (University of Innsbruck) claimed that scientists are
successful in creating the first Qubyte, or series of 8 Qubits, in
which ion traps were used.
In 2006 Scientists in Waterloo and Massachusetts found
methods to control on a 12-qubit system. Quantum
computation related control becomes more complex with the
increase of Qubits.
In 2007 Canadian start up company D-Wave created a 16-
qubit quantum computer. The computer solved many pattern
matching problems.
IV. QUANTUM LANGUAGES
Quantum Computation involves some new concepts which
are related to the movement of the particles like entanglement.
So the Quantum programming language should be able to deal
with these concepts. [6]
A quantum language QML is introduced which provides
some practical semantics which could be understood by the
quantum logic gates. [7]
The standard semantics are not compatible with the
Quantum Mechanics due to its limitations but using semantic
realism this difference can be removed. One can generate a
Quantum Language which contains the Lindenbaum-Tarski
algebra which is compatible to Quantum Language. [8]
Conventionally the quantum languages are defined at the
low level and which discourages the normal programming
practices so a new high language is described which has
proper properties of a language. [9]
The Quantum Languages are continuously evolving and
new dimensions are being added resulting in more structures
and high level languages but still there is lot to do.
V. HIGH PERFORMANCE QUANTUM COMPUTING
Various problems which need intensive computation will
be solved by high performance Quantum computing. The
High performance computing will get sustainable performance
and will result in 1x 1015
floating point operations per second.
[18] The super computers having powers of petascale during
the processing of some applications can reach to one
quadrillion FLOPS. [18]
In the paper a parallelization solution is implemented,
simulating the quantum computers related memory bounding
problem, the technique is based on hybrid handling of MPI
and OpenMP communication which used different threads.
[19] An algorithm built for the purpose and which uses 1 to 2
QBIT gates works very well with IBM p690 having 1024
processors and 3TB of memory. [19]
Fig. 6 Partitioning of 3d Global lattice for a HPQC
mainframe. [20]
The global lattice shown above measures 4000 x 500,000
unit cells and it is prepared using approximately 7.5 x 109
photonic chips. [20]
[20] Have initiated the idea of a High Performance
Quantum Computer, the quantum computer uses a 3
dimensional cluster lattice for processing multiple user related
information.
VI. CAPABILITIES AND LIMITATIONS
Quantum computers have lots of capabilities and they can
solve problems with no time which a classical computer can
take years to solve. Quantum computers can perform multiple
transactions at one time as compared to the classical
computers.
On the other hand the quantum computers are still evolving
and they are not as much scalable yet. We should not expect
magical things from quantum computers and we should not be
too optimistic regarding quantum computers because they
might let us down. [14] Noise distortion can lead to
information corruption. Different implementations of
Quantum Computers have been developed but they are of
limited use and simply only for certain type of demonstration.
A. Cryptography and Quantum Computing
The traditional cryptographic processes and procedures are
more secured using Quantum cryptography as the
conventional system needs one time key exchange for a secure data exchange which can be achieved by the quantum
communication channel.
The BB84 protocol is used for key exchange and the
method is divided in two stages and the communication
between the two sites is done over a quantum and public
channel respectively. [21] The protocol detects snooping if
someone tried to hack the network with some very high
precision. [21]
It is not yet discovered that how the classes BQP is related
to others such as BPP, UP and N. If Quantum computers
become reality then the cryptosystems such as RSA will be
compromised and some will not be challenged and for the
compromised one replacement algorithms will be designed.
[22]
The quantum superposition rule has enabled new
capabilities which are far more than the conventional
techniques for information extraction and sharing. [10] The
cryptography in quantum computing can let both parties to
exchange keys in the presence of some hacker. [10]
The quantum systems are prone to de coherence. Due to
perturbations from the environment qubits get flipped or
corrupted which will result in the loss of data. The current
procedures used in quantum communication lacks the devices
which can regenerate the signals if proper devices will not be
used then the original signal can be destroyed or completely
changed, If somehow some procedure is developed to amplify
the signal then the same procedure can be used for hacking the
signal.[21]
B. Quantum Algorithms
The quantum computing is related with foundations of
mathematics and physics. Grover’s search uses different
technique for speeding up traditional algorithms on quantum
computers. [15]
The Simon’s Algorithm shows that BQP is firmly larger
than BPP and on the other hand factoring algorithm is not
convincing in this matter but quantum factoring is more
related to public key cryptography and quantum factoring has
gathered a huge attention to the field of quantum computing.
[24]
The L. K. Grover’s search algorithm is very important
algorithm regarding quantum computing. Other than search
this algorithm can also be applied to many other problems and
it can increase the speed up to square root. If we are searching
in a database a search speed up by square root can make the
system very efficient. [24]
Optimal quantum query algorithms for eulerian graph and
project scheduling is developed along with the improvement
in salesman problem quadratic degree faster having maximal
degrees of three, four or five. [25]
Some open problems like Boolean matrix product regarding
tight time space tradeoffs and Boolean matrix vector and
matrix product tradeoffs need to be researched for both
classical and quantum computers. [26]
A new algorithm for Boolean Matrix Multiplication
regarding query complexity and time complexity is presented
by [27], the complexity calculated for the algorithm regarding
n x n Boolean matrix is Ō(n3/2
+ nl
3/4
), where l is related to
entries which are not zero. This algorithm improves the
algorithm created by Buhram and Spalek which has a time
complexity of Ō (n3/2
√l). [27]
C. Security and Quantum Computing
Classical computation and security technologies are a
viable solution for the current environments but in future
when quantum computers will be operational then a lot of
changes will be required regarding security and
communications. [11]
In [29] notions regarding message attack related to
signatures and encryption related cipher text attack are defined
and then these are used for the signatures and encryption
schemes construction. For signatures it is proved that they can
be constructed from any has function which is collision
resistant and for encryption it is proved that they can be
constructed from public key and symmetric key. [29]
Adversaries in quantum computation are also controllable
as they are in the classical computation, but the classical
computation will become insecure if contacted with quantum
adversaries. [30]
Three main reasons are the cause that Quantum
cryptography is much more secure than the classical
computation. Firstly the unknown quantum state cannot be
cloned so no one can take advantage of the unknown state,
secondly any attempt to calculate and measure the quantum
state will make a disturbance in the system so any message
which is intercepted by some eavesdropper will become
infected and will be of no use for the recipient, thirdly if some
quantum property is measured and changed it can’t be
reversed to its original state, so these three properties gives
power to the quantum computation and make it secure from
any eavesdropper. [31]
High level research is required in order to standardize the
quantum information and related protocols and quantum
computing related physical layer implementation. [32]
The hardware which will be required for quantum
computation will be similar to QKD communication
systems.QKD and quantum communication both require
receivers and transmitters for weak signals or single photon.
[32]
Fig:7 The cyber-physical monitoring system and quantum seal
integration. [32]
The eavesdropping and tempering of the quantum signals
can be trapped by the quantum seal which uses the unique
structure of the quantum signals, but for this security quantum
transmitters and receivers will be required. [32] D. Complexity and Quantum computation
Computational constraints and problems are considered in
computational complexity in relation with the time consumed
or number of processing steps. [13] Any random access
machine or probabilistic Turing machine can be used to
simulate any physical implementation of computing devices
with polynomial factor overhead. [13]
There are arguments that famous Church Turing problem
cannot be solved using quantum mechanics. [13]
The complexity theory practitioners give a lot of
importance to the Quantum computation, they are not only
working on the computational complexity but also on
quantum interactive proof systems and quantum related NP.
[33]
The graphs related quantum complexity is a new area of
research. Quantum query and quantum time complexity is
being studied as a part of quantum complexity measures. [34]
The query complexity of a graph algorithm refers to the
number of queries adjacency list of the graph or adjacency
matrix and quantum time complexity is related to the basic
quantum operations. [34]
VII. PRACTICAL QUANTUM COMPUTERS AND RELATED
RESEARCH
D-Wave is the first of its kind commercial quantum
computing company which is founded in 1999. D-Wave is
now leading in the fabrication, development and integration of
quantum computers. The customers of D-Wave include USC,
Google, NASA and Lockheed-Martin. [35]
The people at D-Wave had worked for five years only
gathering information to how to build a quantum computer.
They focused on how to design, manufacture and scale the
quantum computer into realization. [35]
Along with the quantum computers different layers of the
software are also designed in order to operate on the new
hardware and the architecture. The work has also done for
solving the industry scale related learning, classification and
optimization problems. [35]
The researchers at University of Waterloo are working on
the laws of nature related to quantum theory so that new
powerful technologies can be developed which in result will
help in developing future economies. [28] Extensive research
is going on at Waterloo regarding quantum error correction
and fault tolerance , quantum complexity, quantum algorithms,
quantum information theory, spin based quantum information,
non electronics related quantum information processing,
optical information processing related to quantum theory and
quantum cryptography. [28]
CONCLUSIONS
The quantum computers are a great prospect and it will
solve many problems which cannot be solved by traditional
computing. The hardware and programs related to Quantum
computing are still evolving but soon it will become a reality
and will change the technology scene.
The research work is being done in quantum languages and
quantum algorithms in order to develop new languages for the
quantum computers. The work is also being done in relation to
the security and complexity of the quantum computation in
order to get secure and reliable quantum systems.
Quantum computers when realized will change the entire
concept of computing, the speed and the computation will
increase by many times. The hardware, programming
languages and algorithms will also change. The measures for
security, complexity and cryptography will also change. So
the quantum computers will change everything related to
computers as we know it. It will create lot of new
opportunities related to jobs and business. It will generate lot
of money and economies will flourish. New research areas
will open the doors for new inventions. The problems which
seem not solvable through traditional computing stand a very
good chance to give results using quantum computing.
Every field of life including research, education,
engineering, aero-space, medical, technology, media, nuclear
technology, space travel, armed forces and sports, in fact
every field of life will be affected by the quantum computers.
Practical quantum computers are also being developed at
D-Wave, which are serving great purpose in different
multinational corporations. Extensive research is also going
on at University of Waterloo related to quantum computation.
ACKNOWLEDGMENT
I acknowledge my respected teacher who is supervising this
project and will guide and help me to improve this research
paper.
REFERENCES
[1] Simon J. Devit, William J. Munro, and Kae Nemoto, High
Performance Quantum Computing, arXiv.org, October 14 2008.
[2] Norman Margolus , Parallel Quantum Computation, March 3, 1994.
[3] Norman Margolus, Quantum Computation, January 1986.
[4] David P. DiVincenzo, The Physical Implementation of Quantum
Computation, arXiv.org, version3, April 13 2000.
[5] D. Kielpinski, C. Monroe and D.J. Wineland, Architecture for a large-
scale ion-trap quantum computer, NATURE Journal of Science , June
13, 2002.
[6] Peter Selinger, A Brief Survey of Quantum Programming Languages,
Springer 2004.
[7] Altenkirch, Thorsten, A functional quantum programming language,
arXiv.org , version 5, April 19, 2005.
[8] Claudio Garola, Physical Propositions and Quantum Languages,
arXiv.org, November 22, 2006.
[9] Peter Selinger ,Towards a quantum programming language, ACM
Digital Library Volume 14 Issue 4, August 2004
Pages 527 - 586.
[10] Richard J. Hughes, Cryptography, Quantum Computation and Trapped
Ions. SPIE Digital Library, May 15, 1998.
[11] Jim Alves-Foss, Security Implications of Quantum Technologies, 21st
NISSC Proceedings, October 1998.
[12] Marius Nagy and Selim G. Akl, Quantum computing: Beyond the
limits of conventional computation. July 22 2005.
[13] Umesh V. Vazirani, A Survey of Quantum Complexity Theory,
Proceedings of Symposia in Applied Mathematics, 2002. [14] Scott Aaronson, The limits of Quantum Computers, Scientific
American, March 2008.
[15] Peter W Shor, Introduction to quantum Algorithms, arXiv.org ,
Version2, July 6,2001.
[16] http://en.wikipedia.org/wiki/Qubit
[17] Diederik Aerts and Bart D’ Hooghe, Quantum Computation: Towards
the Construction of a between Quantum and Classical Computer.
Published by World Scientific Publishing Co. Pte. Ltd., 2002.
[18] Sergey Edward Lyshevski, High Performance Computing and
Quantum Processing. 2012.
[19] Guido Arnold, Marcus Richter, and Thomas Lippert, High
Performance Simulation of Ideal Quantum Computers, NIC Series, Vol.
32 ISBN 3-00-017351-X, pp. 349-356, 2006.
[20] Simon J. Devit, William J. Munro, and Kae Nemoto , High
Performance Quantum Computing, Progress in Informatics, No. 8, pp.
1-7, (2011) .
[21] Hidayath Ansari, Aditya Parameswaran, Lakulish Antani,Bhaskara
Aditya,Ankur Taly and Luv Kumar, Quantum Cryptography and
Quantum Computation.
[22] Marco A. Barreno, The Future of Cryptography Under Quantum
Computers. July 21 , 2002.
[23] Antal Nemes, Quantum, Resistant Cryptography. Budapest 2012.
[24] Peter W. Shor, Introduction to Quantum Algorithms. Version 2, July 6
2001.
[25] Sebastian Dorn, Quantum Algorithms for Graph Traversals and
Related Problems.2009.
[26] Robert Spalek, Quantum Algorithms , Lower Bounds and Time-Space
Tradeoffs. arXiv.org Version 2, May 9, 2006.
[27] Francois Le Gall, Improved Ouput-Sensative Quantum Algorithms for
Boolean Matrix Multiplication. arXiv.org Version 2 , December 20,
2012.
[28] https://uwaterloo.ca/institute-for-quantum-computing/
[29] Dan Boneh, Mark Zhandry, Secure Signatures and Chosen Ciphertext
Security in Quantum Computing World. CRYPTO 2013 33rd
International Cryptology Conference.
[30] Renato Renner, Information Security in a Quantum World. Springer
Volume 7119, 2012, pp 57-62.
[31] Bruce R. Aubum, Quantum Encryption – A Means to Perfect Security ,
SANS Institute 2003.
[32] Travis S. Humble, Quantum Security for the Physical Layer , IEEE
Communication Magazine , August 2013.
[33] Lance Fortnow, One Complexity Theorist’s View of Quantum
Computing. arXiv.org, March 9, 2000.
[34] Sebastian Dorn, Quantum Complexity Bounds for independent set
Problems, arXiv.org, Version 3, February 28, 2007.
[35] http://www.dwavesys.com/our-company/meet-d-wave