Computation, Quantum Computing & Grover’s Algorithm
High-Level Guiding Questions
Here’s a list of guiding questions I created to structure my presentation. The answers are only meant as an idea of what might constitute an answer, since most of the class was structured as a discussion rather than a lecture.
What can a computer do?
Perform computations. Which means for a given input, perform rules, return output.
2. What kinds of problems can computers solve?
Decision, search, and optimization problems.
3. How do we define a computer mathematically? How do we know the limits of computers?
Turing machines.
4. How can we rigorously define computational difficulty?
Complexity classes.
5. In quantum computing, we can manipulate 2^n amplitudes. This seems like exponential progress. However, we’re still unsure whether quantum computers can solve problems that classical computers cannot. What property of quantum computing is the most difficult to overcome?
We cannot observe these amplitudes individually. We can only measure one result.
Discussion Outline
What can a computer do?
Types of problems: decision, search, optimization, etc.
Turing machines are a definition of a computer, which gives us grounding for a universal notion of classical computing
Complexity classes:
Constant time
P - polynomial time
QP - quasipolynomial time
SUBEXP - subexponential time
E - exponential time
BQP - bounded-error quantum polynomial time
Grover’s Search Algorithm
Problem statement: Find the unique value to a black-box function that produces a particular output value
Classical algorithm: Search the entire space.
Classical analysis: O(2^n = N)
Quantum algorithm: [Depicted Below]
Quantum analysis: O(2^(n/2)) = sqrt(N))
Conclusion: We still aren’t sure of the relationship between BQP and P.
