Quantum Computing and Communications

An Engineering Approach

Sandor Imre, Ferenc Balazs

• Publisher: Wiley
• Year: 2013
• ISBN:
  9781118725474
• Edition: 1
• Topic: Computer Science
• Subtopic: Computer Engineering
• Index: Computer Science

Quantum computers will revolutionize the way telecommunications networks function.

Quantum computing holds the promise of solving problems that would be intractable with conventional computers by implementing principles from quantum physics in the development of computer hardware, software and communications equipment.

Quantum-assisted computing will be the first step towards full quantum systems, and will cause immense disruption of our traditional networks. The world's biggest manufacturers are investing large amounts of resources to develop crucial quantum-assisted circuits and devices.

Quantum Computing and Communications:

• Gives an overview of basic quantum computing algorithms and their enhanced versions such as efficient database searching, counting and phase estimation.
• Introduces quantum-assisted solutions for telecom problems including multi-user detection in mobile systems, routing in IP based networks, and secure ciphering key distribution.
• Includes an accompanying website featuring exercises (with solution manual) and sample algorithms from the classical telecom world, corresponding quantum-based solutions, bridging the gap between pure theory and engineering practice.

This book provides telecommunications engineers, as well as graduate students and researchers in the fields of computer science and telecommunications, with a wide overview of quantum computing & communications and a wealth of essential, practical information.

Part I

Introduction to Quantum Computing

1

Motivations

1.1 LIFE CYCLE OF A WELL-KNOWN INVENTION

Every invention/technology has its own life cycle, similar to a human being. It can be shorter or longer but all of them have common phases and stages. Let us summarize this evolution using the well-known example of steam engine. First, scientists spend lots of time to find out something new. In our case Heron, a most famous experimenter, designed and implemented a steam-engined ball named Heron’s ball (see Fig. 1.1).

Once a new idea has been born a long period of time is required until the stage when size, cost, efficiency, etc. of pieces of this equipment reach a minimally required and acceptable level. Many amateurs and experts devote their life to fulfil these requirements representing the childhood of the technology. The way is paved with many failures and rare successes therefore most of them remain anonymous forever. However, one day a clever guy manages to combine the small pieces of former results and adds something to them thus finally he/she succeeds. Concerning our example James Watt built the first working steam engine in 1765. Thanks to Mr. Watt steam technology attained its majority.

In the third phase the technology emerges from the deep of dark and mysterious laboratories and begins spreading among everyday people. Fulton’s ship Clermont in 1807 irreversibly ended the glorious age of sailing ships and men of war while Stephenson’s Rocket in 1829 convinced the skeptics that railway would be the leading transportation solution on land in the future. Human, sail and animal power had been replaced by steam engines during some decades from the kitchens via workshops up to enormously large ships such as Titanic or the battleships of World War I. The efficiency of the largest steam engine reached 22000 kW in 1941. Of course to achieve this level of popularity geniuses have to overcome strong resistance from those who exert the power. For instance William Symington built a steam-engined towboat on the Thames and presented her capabilities. Unfortunately the officials prohibited Symington from using the boat because they were afraid that the waves generated by the boat might damage the river-bank.

Fig. 1.1 Heron’s ball about 100 B.C.

The size/power in itself is, however, not enough to survive (cf. dinosaurs or large empires). After a certain point efficiency becomes as important as power. It was foreseen and proven theoretically – long before steam-powered systems reached the top – that the efficiency of any steam-engine is limited and not enough for example for flight. If the new demand cannot be satisfied by means of a certain technology then other, even very young ideas are brought to light while the old one will be squeezed gradually. The reader may guess the name of the new pretender: yes, it was the internal combustion engine.

1.2 WHAT ABOUT COMPUTERS AND COMPUTING?

Now let us turn to our ‘home’ science which focuses on computers, computing and communications. The most important steps towards an electronic computer were done during World War II when the large number calculations in the Manhattan project required an elementary new equipment which was fast enough and adaptive (programmable). Many clever scientists were engaged with this problem. We mention here the polymath Neumann because he will appear several times in this book. As we will see later he played important role in quantum mechanics as well but at this moment we say thank you to him for the invention of the ‘control by stored program’ principle.¹ This principle combined with the vacuum tube hardware which formed the basis of the first successful computers.² Unfortunately the tubes strongly limited the possibilities of miniaturization hence the first computers filled up a whole room, which strongly restricted their wide applications. Therefore scientists paid attention to the small-scale behavior of matter. Fortunately the invention of semiconductors and the appearance of the transistor in 1948 by Bardeen, Brattain and Schockley opened the way to personal computers and other handheld equipment.

One day in 1965 when Gordon Moore from Intel was preparing his talk and started to draw a plot about the performance of memory chips he suddenly observed an interesting rule called Moore’s law. As it is depicted in Fig. 1.2 he concluded that since the invention of the transistor the number of transistors per chip roughly doubled every 18–24 months, which means an exponential increase in the computing power of computers. Although it was an empirical observation without theoretical proof the law seems to be still valid nowadays. However, similar to the case of steam engine farseeing experts tried to determine the future of this technology. They estimate serious problems around 2015. What reasons may stand behind this prophecy?

No matter how surprising it sounds this trend can be traced back simply to drawing lines. The growth in processors’ performance is due to the fact that we put more and more transistors on the same size chip. This requires smalle...

Table of contents

• Cover
• Contents
• Title Page
• Copyright
• Dedication
• Preface
• How to use this Book
• Acknowledgments
• List of Figures
• Acronyms
• Part I: Introduction to Quantum Computing
• Part II: Quantum Algorithms
• Part III: Quantum-assisted Solutions of Infocom Problems
• Part IV: Appendices
• References
• Solutions of Exercises
• Index