) = ao|0) + Q i | l ) . Similar to orthonomal bases of a vector space, the observables are completely arbitrary. One may exchange the role of |0) and |1). We can also choose to operate on the rotated basis {^ ( |0 ) + |1)), ^ ( | 0 ) — |1))}- The choice of our observables depends only on how we build our measurement device. We have portrayed a qubit as a generalized binary random variable. How-ever, a qubit cannot be reused. By the No-Cloning theorem [11] one cannot back up a qubit for future uses. We understand that measurements collapse the state of a qubit and subsequent measurements will always end with the same outcome. For instance, suppose we start with a qubit with state |) = ^(%/2|0) + We have with probability two thirds measuring state 0 and probability one third Chapter 2. A brief introduction to Quantum Computing 17 measuring state 1. However, once we measured 0, we stayed 0 all the time. Fu-ture measurements must always agree with the first measurement. If we measure 1 from the qubit for the first time, we would have collapsed the state to contian only |1) for all remaining computation. In some implementation, the.measure-ment operation is so destructive that the qubit itself is destroyed and further measurements would not even be possible. As a result, we have to reprepare the qubit before we can perform the same measurement. This concept can be extended to system with arbitrary number (> 1) of levels. A qubit is a device capable of encapsulating a two level system. A se-quence of qubits makes a quantum register. Concatenating qubits provide a system with exponential number of levels. For instance, an k bit register can represent 2 f c integers. Wi th k qubits, we can have 2k different observables, in-cluding |0) |0). . . |0), |0}|0). . . |1), . . . , etc. For simplicity, we write |0) |0) . . . |0) as [00 . . . 0). Similarly, we can write |00 . . . 1) or |00 . . . 10). Since these are basi-cally binary numbers, we will also use the notation |0), |1), |2), etc. Generally, if we have k bits, we would have |0) up to \2k — 1). These 2 f c states provides a basis for the concatenated multi-level system. A quantum computer refers to a collection of qubits / quantum registers and devices to manipulate them. 2.3 Unitary Transform and Entanglement The state of a probabilistic (quantum) system can be described by a vector of probabilities (amplitudes). Different states are isolated and progress inde-pendently. A probabilistic system evolves through a series of redistribution of probabilities. When we perform any operation (state transition) on an n-level Chapter 2. A brief introduction to Quantum Computing 18 system, we can express that as: P0,0 Pl,0 P0,1 P l , l P0,n-1 Pl,n-1 \ / CO \ C l V Cn-1 ) \ Pn-1,0 Pn-1,1 P n - l , n - l / \ Cn-1 j This transition matrix means that if my system is in state i, it has probability Pij to evolve into state j. A valid transition matrix must preserve the probability of each state, giving the formula _j Pi,j = 1- Such a matrix is called a Markov matrix. The general idea applies in the quantum setting. We have different basis states and they operate independently and linearly. Instead of using probabili-ties, the transition matrix is replaced with one that contains complex entries. A valid transition must preserve the amplitude and ensure that YDi l a * | 2 = 1 after the transition. It turns out that such a transition must be unitary. Given any unitary transition matrix A, we have A-1 = A^ where A^ denotes the adjoint (conjugate tranpose) of A. This also implies that all allowed transitions are inherently invertible. This is clearly not required in the classical case. Some basic single qubit operators include I = / 1 0 0 1 X = ( 0 1 1 0 Y = 0 - i 1 0 Z = 1 0 0 -1) Consider the basic operation X. Given the single-qubit state \