Quantum Computation: A Computer Science Perspective

Anders K. H. Bengtsson

Abstract:

The theory of quantum computation is presented in a self contained way from a computer science perspective. The basics of classical computation and quantum mechanics is reviewed. The circuit model of quantum computation is presented in detail. Throughout there is an emphasis on the physical as well as the abstract aspects of computation and the interplay between them.

This report is presented as a Master’s thesis at the department of Computer Science and Engineering at G{\”o}teborg University, G{\”o}teborg, Sweden.
The text is part of a larger work that is planned to include chapters on quantum algorithms, the quantum Turing machine model and abstract approaches to quantum computation.

More detail see paper (pdf)

Photonic quantum technologies

Photonic quantum technologies could be only light years away from PhysOrg.com
Photonic quantum information science could soon move out of the laboratory and be used in future technologies like quantum computers thanks to a grant of over £1 million.

[...]

New Quantum Key System Combines Speed, Distance

Researchers at the National Institute of Standards and Technology (NIST) have built a prototype high-speed quantum key distribution (QKD) system, based on a new detector system that achieves dramatically lower noise levels than similar systems. The new system, they say, can perform a theoretically unbreakable “one-time pad” encryption, transmission and decryption of a video signal in real-time over a distance of at least 10 kilometers.

Key distribution—the problem of ensuring that both the sender and receiver of an encrypted message (and no one else) share the same long string of random digits (the so-called “key”) used to encode and decode the message—has always been one of the most important challenges in cryptography. Since the 1980’s it’s been recognized that the unique properties of quantum mechanics—the fact that certain measurements cannot be made without altering the thing measured—offered the possibility of a system that could transmit as long a key as desired between two parties with no chance that it could be copied undetectably by a third party.

Detection stage of the NIST prototype quantum key distribution (QKD) system: Photons are “up-converted” from 1310 to 710 nm by one of the two NIST-designed converters at right, then sent to one of two commercial silicon avalanche photo diode units to the left.

Since then the race has been on to build a fast, practical and reliable QKD system. One important requirement for any candidate system is that it be compatible with existing fiber-optic telecom networks that transmit at wavelengths of either 1550 or 1310 nanometers (nm) to reach the greatest distance. Another requirement is a highly efficient photon detector that can detect single photons reliably without introducing significant amounts of “noise.” One of the best low-noise detectors, a silicon-based avalanche photo diode (Si-APD), does not function at the telecom wavelengths. Instead, it operates best at much shorter wavelengths around 700 nm. To take advantage of the Si-APD, the NIST group designed a sub-system to “up-convert” single photons from a transmission wavelength of 1310 nm to 710 nm for high-efficiency detection.

Their QKD system that incorporates this up-conversion technique, described in a recent paper,* generates and transmits secure keys at a rate of over half a million bits per second over 10 km of optical fiber, fast enough to encrypt streaming digital video using one-time pad in real time. The group also has transmitted secure keys at rates near 10 kilobits per second at five times that distance. The same team last year set a speed record for transmission of secure keys over a kilometer of fiber (see www.nist.gov/public_affairs/releases/quantumfiber.htm). This work improves the distance by at least 10 times.

Advantages of the new system, according to the research team, include high speed, high efficiency, low noise and convenience of operation. The fact that it uses a 1310 nm transmission wavelength somewhat limits the propagation distance but adds the advantage that the parallel “classical-quantum” communication, which is needed for a full QKD system, can be realized in a single fiber without significant interference. Details of NIST’s up-conversion QKD research are available at http://w3.antd.nist.gov/quin.shtml.

Pemrosesan Informasi Kuantum pada Intan (Diamond)

Komputasi Kuantum merupakan suatu bidang multidisplin dan menarik, yang telah menjadi fokus peneletian baik eksperimental maupun teoritis dalam sepuluh tahun terakhir. Diantara sistem-sistem yang diusulkan, misalkan model iop-traps atau rangkaian superkonduktor, Qubits berbasis keadaan padat (solid-states) diasumsikan menjadi kandidat yang menjanjikan bagi pengujian pertama dari Hardware Kuantum.

Peneliti-peneliti dari 3. Physikalischen Instituts Universität Stuttgart dan Harvard University, telah berhasil dalam eksperimennya, yaitu bagaimana cacat titik (poin defect) pada intan (diamond) dapat berfungsi dengan baik sebagai prosessor yang sangat kecil dari kompute kuantum.

Qubits didefinisikan sebagai keadaan spin tunggal (elektorn atau inti). Dengan asumsi ini, memungkikan kita mengeksplorasi waktu koheren yang lama (beberapa detik bagi spin inti pada temperatur-temperatur kirogenik). Disamping itu, transisi optik antara keadaan elektronik dasar dan tereksitasi memungkinkan koppling antara derajat kebebasan spin dengan keadaan medan elektromagnetik. Koppling yang demikian memungkinkan akses keadaan spin ‘read-out’ melalui hamburan foton spin-selective. Konsekuensi logis, kita dapat menggunakan keadaan spin sebagai ‘robust memory’ bagi “flying qubits (foton)”.

Detailnya dapat dilihat disini:

• 3. Physikalisches Institut, Universtität Stuttgart:
  http://www.pi3.uni-stuttgart.de
• AG Fedor Jelezko:
  http://www.pi3.uni-stuttgart.de/ags/jelezko/
• http://arxiv.org/abs/quant-ph/0510152

Experimental Realization of Deutsch’s Algorithm in a One-way Quantum Computer

M. S. Tame, R. Prevedel, M. Paternostro, P. Böhi, M. S. Kim, A. Zeilinger

Abstract: We report the first experimental demonstration of an all-optical one-way implementation of Deutsch’s quantum algorithm on a four-qubit cluster state. All the possible configurations of a balanced or constant function acting on a two-qubit register are realized within the measurement-based model for quantum computation. The experimental results are in excellent agreement with the theoretical model, therefore demonstrating the successful performance of the algorithm.

paper ps, pdf

Comment from Physorg.com here

Quantum computer set up. Image credit: Mark Tame.

 

Finding a way to build a quantum computer that works more efficiently than a classical computer has been the holy grail of quantum information processing for more than a decade. “There is quite a strong competition at the moment to realize these protocols,” Mark Tame tells PhysOrg.com.
The latest experiment performed as a collaboration by a Queen’s University theoretical group and an experimental group in Vienna has “allowed us to pick up the pace” of quantum computing.

The joint project’s experiment is reported in Physical Review Letters in an article titled, “Experimental Realization of Deutsch’s Algorithm in a One-Way Quantum Computer.”

“This is the first implementation of Deutsch’s Algorithm for cluster states in quantum computing,” Tame explains. Tame along with members of the Queen’s group in Belfast, including Mauro Paternostro and Myungshik Kim joined a group from the University of Vienna, including Robert Prevedel, Pascal Böhi, and Anton Zeilinger (who is also associated with the Institute for Quantum Optics and Quantum Information at the Austrian Academy of Sciences) to perform this experiment. see more http://www.physorg.com/printnews.php?newsid=96107220

Quantum Discrete Cosine Transform for Image Compression

Chao Yang Pang, et.al

Abstract: Discrete Cosine Transform (DCT) is very important in image compression. Classical 1-D DCT and 2-D DCT has time complexity O(NlogN) and O(N²logN) respectively. This paper presents a quantum DCT iteration, and constructs a quantum 1-D and 2-D DCT algorithm for image compression by using the iteration. The presented 1-D and 2-D DCT has time complexity O(sqrt(N)) and O(N) respectively. In addition, the method presented in this paper generalizes the famous Grover’s algorithm to solve complex unstructured search problem.

file here ps, pdf

Microchip-falls for Quantum Computer

Ulmer physicist realized the first microchip-falls in Europe, which is used for experiments on the way to the scalable quantum computer.

At Institut for quantum data processing of the University of Ulm Stephan Schulz and Ferdinand Schmidt Kaler realized first microchip-falls in Europe, which is used for experiments on the way to the scalable quantum computer.

The prototype of the three-dimensional linear microchip-falls stores individual Ca+ ions, which are arranged like beads on a chain. Each individual ion represents a quantum bit, similarly to the bits of an everyday computer. The future quantum computer will solve unsolvable problems made of computer science and natural science with unusual arithmetic performances by the use of the quantum bits.

In the new microchip-falls the Ca+ ions are stored by electrical fields. A multiplicity of individual control segments permitted for the first time parallel the allocation of the ion chains into separated single ions, which are shifted controlled by electrical tensions. For the operations of the quantum computer individual ions with laser pulses are manipulated and the result of computation is optically picked out.

Fig.: That microchip has a size of 11×11 mm2 and consists of 64 separately controllable electrodes. It is operated with a frequency by 24 MHz in the ultra high vacuum. (Source: University of Ulm)

 

 

The new microchip-falls is world-wide singular due to the number of their control segments. Thus it orders over a separate memory and processor range around the scaling barness of a quantum computer with individual ions to demonstrate for the first time. A goal is the storage and processing of approximately 100 quantum bits - according to an efficiency, which exceeds each conventional computer far.

This the Universtität Ulm-developed quantum devices are the reference design for the development of scalable ion quantum computers, promoted by the European Union. Similar devices are likewise developed at present in the USA.

Source: University of Ulm

Further information:

* Quantum data processing, University of Ulm: http://www.uni-ulm.de/qiv/

Quantum existence testing gives extreme solutions to increase network speed

by Liza Zyga

http://www.physorg.com/news93787328.html

Using a novel quantum computing algorithm, scientists have simplified the process for finding extreme values in a database compared with classical and earlier quantum computing methods. With its reduced time and minimal error probability, this quantum process could significantly increase the speed of computing in global and mobile networks.

Sándor Imre, an engineer at the Budapest University of Technology, calls this new computing process “quantum existence testing,” which is a special case of quantum counting. The quantum existence testing algorithm searches unsorted databases to find extreme values, attesting to the intriguing powers of the quantum mechanical effects of parallel processing.

“Compared to classical solutions, the improvement with quantum existence testing is about the square root of N in the case of a database N entry of length,” Imre explained. “For example, if you are able to classically find an extreme value in a database containing 1000 entries in 1 second, then the quantum alternative can handle 1000 such databases during the same time, or a database with 1 million entries.”

Kotak Einstein

Tahun 1927 dalam kerangka ‘ekperimen teoritis’, Einstein mengusulkan sebuah ‘box’ (kotak Einstein kita boleh sebut), di dalamnya kita menjebak sebuah berkas cahaya dan kemudian berkas partikel tunggal (foton) akan di pancarkan, dengan tujuan untuk mengukur hubungan antara massa dan energy.

Delapan puluh tahun kemudian, fisikawan Perancis (Laboratoire Kastler Brossel, part of France’s National Centre for Scientific Research (CNRS), in its Cavity Quantum Electrodynamics lab.) berhasil merealisasikannya, ukurannya 2,7 cm dan mampu menangkap foton, memungkinkannya untuk dapat memonitor foton dari awal pemunculan sampai ia menghilang.

Penemuan ini akan membantu dalam pengembangan penting bagi ‘high performance computers dan quantum computing’ masa depan, — dan tentunya bagi bidang fisika.

Gambar di bawah ini set-up eksperimental (Credit: Laboratoire Kastler Brossel). “Samples of circular Rydberg atoms are prepared in the circular state g in box B, out of a thermal beam of rubidium atoms, velocity-selected by laser optical pumping. The atoms cross the cavity C sandwiched between the Ramsey cavities R₁ and R₂ fed by the classical microwave source S, before being detected in the state selective field ionization detector D. The R₁–C–R₂ interferometric arrangement, represented here cut by a vertical plane containing the atomic beam, is enclosed in a box at 0.8 K (not shown) that shields it from thermal radiation and static magnetic fields.”

Penelitian ini telah dipublikasi di Nature dengan judul “Quantum jumps of light recording the birth and death of a photon in a cavity” (Volume 446, Number 7133, Pages 297-300, March 15, 2007). Dua links ke the abstract dan ke the full paper, dimana gambar di atas diperoleh(PDF format, 5 pages, 297 KB, via arXiv.org).

A Single-Photon Server with Just One Atom

Every time you switch on a light bulb, 10 to the power of 15 (a million times a billion) visible photons, the elementary particles of light, are illuminating the room in every second. If that is too many for you, light a candle. If that is still too many, and say, you just want one and not more than one photon every time you press the button, you will have to work a little harder. A team of physicists in the group of Professor Gerhard Rempe at the Max Planck Institute of Quantum Optics in Garching near Munich, Germany, have now built a single-photon server based on a single trapped neutral atom. The high quality of the single photons and their ready availability are important for future quantum information processing experiments with single photons. In the relatively new field of quantum information processing the goal is to make use of quantum mechanics to compute certain tasks much more efficiently than with a classical computer. (Nature Physics online, March 11th, 2007)

Fig.: A single atom trapped in a cavity generates a single photon after being triggered by a laser pulse. After the source is characterised, the subsequent photons can be distributed to a user.

Image: Max Planck Institute of Quantum Optics

more detail see here

This research work has been published as an advance publication by Nature Physics under the name “A single-photon server with just one atom” on March 11, 2007. Here is a link to the abstract. You also can read the full paper (thanks to arXiv.org).