DOC PREVIEW
TAMU CSCE 689 - chapter2

This preview shows page 1-2-19-20 out of 20 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

QuantumAlgorithmsAndreas Klappenecker Texas A&M UniversityLecture notes of a course given in Spring 2003. Preliminary draft.c 2003 by Andreas Klappenecker. All rights reserved.PrefaceQuantum computing provides a fresh perspective on information processing.Some quantum algorithms have the promise to possibly provide an exponen-tial speed-up over classical deterministic and randomized algorithms, whichexplains the massive worldwide efforts to build a viable quantum computer.However, this is by no means the only motivation. Quantum computing hasserious repercussions on classical computing as well.These lecture notes provide a rapid introduction to the main ideas behindquantum algorithms. The subject matter is not difficult, but dramaticallydifferent from its classical counterpart. We provide numerous very simpleexercises that are designed to ease the transition into the quantum realm.Solving the exercises will help to gain an active working knowledge.Our approach is largely based on the quantum circuit model, which iseasy to understand. This model abstracts from the nature and the dynamicsof the physical system realizing the quantum computer. The advantage of thisapproach is that within an extremely short period of time it will be possibleto cover interesting algorithms.The course requires some background in linear algebra. The books LinearAlgebra by Serge Lang and Linear Algebra Done Right by Sheldon Axler areexcellent sources to review such material.Please note that this is a preliminary draft. The lecture notes are incom-plete, and all parts are subject to change. The material should be read inconjuction with the books Quantum Computation and Quantum Informationby Michael Nielsen and Isaac Chuang and Classical and Quantum Computa-tion by Alexei Kitaev, A.H. Shen, and M.N. Vyalyi.If you read these notes, then you have accepted a contract: you agree tocommunicate all errors to me. If you do not want to burden yourself with thistask, then do not read further.Andreas KlappeneckerCollege Station, TexasiChapter 2Quantum CircuitsQuantum computing can be based on various different computational models.The most accessible one is the quantum circuit model, which specifies a se-quence of operations that manipulate the state of the quantum computer atdiscrete time steps. The basic rules of this model are surprisingly simple. Thischapter introduces the basic properties of quantum states, quantum gates, andmeasurements.§1 Quantum StatesA bit has two distinguishable states, denoted by 0 and 1. A classical computermanipulates a set of bits, which form the memory of the computer. Thememory of a quantum computer is based in a similar way on the notion of aquantum bit, qubit for short. A qubit has two clearly distinguishable states,denoted by |0i and |1i. The possible states of a qubit are not exhausted bythese two possibilities. In general, the state of a qubit is of the form a|0i+b|1i,where a and b are complex numbers satisfying |a|2+ |b|2= 1.The states |0i and |1i should be understood as basis vectors of a complextwo-dimensional vector space. We can associate with these states the basisvectors|0i =10, |1i =01. (2.1)The state a|0i + b|1i is a linear combination of these two basis vectors, andis represented by the vector (a, b)t. The operations of the quantum computermanipulate these vectors by linear transformations or by measurements.The value of a quantum bit is always 0 or 1, never anything else. If a qubitis in the state a|0i + b|1i, then this means that the value 0 is observed with12 CHAPTER 2. QUANTUM CIRCUITSprobability |a|2, and the value 1 with probability |b|2. A measurement in thecomputational basis returns the value 0 or 1 according to this rule, and setsthe qubit to the state |0i or |1i, respectively. A consequence is that if themeasurement is repeated, then it will return the same value.It is easy to construct a state that yields a fair coin-flip. Choose the state1√2|0i +1√2|1i. Then 0 and 1 are both observed with probability (1/√2)2=1/2. The resulting state after the measurement is |0i, if the measurementresult was 0, and |1i otherwise.Exercise 2.1 Assume that a qubit is in the state1√10|0i +3√10|1i. What isthe probability to observe 0, or 1, respectively?Exercise 2.2 Assume that a qubit is in the statei√2|0i−1√2|1i. What is theprobability to observe 0, or 1, respectively?A memory consisting of n quantum bits has 2nbasis states, which are de-noted by |0 ···00i, |0 ··· 01i, |0 ··· 10i, . . . , |1 ···11i. The state of the memoryis a linear combination of these basis states. Denote by F2the finite field withtwo elements 0 and 1. An arbitrary state of the memory is of the formXk∈Fn2ak|ki, withX|ak|2= 1.If we read out the memory by a measurement in the computational basis, thenwe will observe the result k, a string of n bits, with probability |ak|2. The scalarcoefficients akare called probability amplitudes or, simply, amplitudes.Exercise 2.3 What is the probability of observing 11, if the memory is inthe state12|00i −12|10i +i√2|11i? In what state is the memory once we haveobserved 11?Exercise 2.4 Describe all possible states of a system of two quantum bitssuch that a measurement in the computational basis yields 00 with probability1/2, and the results 01 and 11 both with probability 1/4.Any quantum system with at least two different basis states can basicallystore a quantum bit, and finding appropriate storage media for a quantumcomputer is a very active area of current research. The linear combinationof basis states reflects the superposition principle of quantum mechanics. Itshould be noted that only the measurement process introduces randomizedbehavior in quantum algorithms. All other operations of a quantum computerare completely deterministic.§2. A SINGLE QUANTUM BIT 3§2 A Single Quantum BitThe operations of a quantum computer allow reading, writing, or manipulat-ing the content of the memory, and therefore serve the same purpose as theoperations of a classical computer. The main distinction is that the opera-tions of a quantum computer are formulated to be conformant with the lawsof quantum mechanics. We explain in this section the basic operations on asingle quantum bit, and introduce some convenient notations.The input operation of a quantum computer can prepare the memory inany basis state. As a result, each quantum bit is either in the state |0i orin the state |1i, but not in a superposition of these basis states. The


View Full Document

TAMU CSCE 689 - chapter2

Documents in this Course
slides

slides

10 pages

riccardo2

riccardo2

33 pages

ffd

ffd

33 pages

intro

intro

23 pages

slides

slides

19 pages

p888-ju

p888-ju

8 pages

w1

w1

23 pages

vfsd

vfsd

8 pages

subspace

subspace

48 pages

MC

MC

41 pages

w3

w3

8 pages

Tandem

Tandem

11 pages

meanvalue

meanvalue

46 pages

w2

w2

10 pages

CS689-MD

CS689-MD

17 pages

VGL

VGL

8 pages

ssq

ssq

10 pages

Load more
Download chapter2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view chapter2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view chapter2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?