wk5

Question 1

what is church Turing thesis

Answer 1

Class of function computable by a Turing machine is the class of functions computable by an algorithm

Question 2

what is the strong church Turing thesis

Answer 2

any model of computation can be simulated by a probabilistic Turing machine with polynomial overhead

Question 3

What is a cnot gate

Answer 3

quantum controlled not

Question 4

what are the 3 operations in quantum circuits

Answer 4

state preparation, unitary evolution, measurment

Question 5

Which gate is this. What happens when value is pi

Answer 5

X gate, if alpha = pi then qubit 0 -> 1, 1->0. A rotation of pi radians to block sphere in x axis

Question 6

which gate is this and how does it behave

Answer 6

Hadamard, qubit 0 into plus state and qubit 1 into minus state

Question 7

what are the |+> and |-> states

Answer 7

|+> = 1/sqrt(2) (|0>+|1>)

|-> = 1/sqrt(2) (|0>-|1>)

Question 8

Which gate is this. What happens when value is pi

Answer 8

Z gate. If state is |1> it makes it into -|1>.It is also also a Not gate in Hadamard basis. Plus to Minus, Minus to Plus

Question 9

what rotation does the not gate do on Bloch sphere

Answer 9

pi radians (180 degrees) on the z axis

Question 10

what does Hadamard do on Bloch sphere

Answer 10

moves qubit around the y axis

Question 11

What is complexity class P

Answer 11

class of all algorithms that can be evaluated in polynomial time on a deterministic turning machine

Question 12

What is complexity class NP

Answer 12

All problems which can be verified in polynomial time. Or problems which may be solved on a non-deterministic turning machine

Question 13

What is complexity class BPP

Answer 13

Bounder Error Probabilistic Polynomial

All problems that may be solved in polynomial time on a non-deterministic/probabilistic turning machine where probability of getting an incorrect result is less than 25%

Question 14

What is complexity class PSPACE

Answer 14

problems decided by a deterministic Turing machine in polynomial time and space

Question 15

what is the relationship between PSPACE, P and quantum computing

Answer 15

PSPACE has more algorithms than P, and quantum computing is in PSPACe

Question 16

What is the class BQP

Answer 16

Bounded-Error Quantum Polynomial (time):

Class of decision problems for which there is a family of polynomial-size quantum circuits which decide the problem correctly with a probability of error of less than 25%

Question 17

How is the complexity of BQP decided

Answer 17

-Size of circuit must be polynomial with respect to the input
-Circuits should be uniformally generated
-there must exist a turning machine that for a given input has a description of the circuit

Question 18

how do we usually determine complexity in quantum algorithms

Answer 18

with respect to the number of calls to some Oracle (a black box sub-routine)