Thursday, January 24, 2019

Notes on Quantum Complexity Theory: Part 1/6

Note: Often in complexity study, I found the term 'conjecture'. It is defined as: "A conjecture is a conclusion or proposition based on incomplete information, for which no proof has been found."

The context of the article is for the circuit model of quantum computation whereby, the qubits are represented by wires and gates are quantum operators.

Quantum Complexity Class
A collection of problems that can be solved by a certain quantum computational model that obeys certain resource (e.g. time) constraints.
E.g. BQP: A quantum complexity class of all decision problems that can be solved in polynomial time by a quantum computer.

Quantum Proof: A quantum proof is a quantum state that acts as witness to a quantum computer that runs verification procedure.
The complexity class QMA is defined by this notion.
QMA contains all the decision problems whose YES-instances are efficiently verifiable by quantum proofs?

Quantum Interactive Proof System: In this system, there is a verifier quantum computer and one or more (quantum state) provers. The system involves processing and exchange of the quantum information between the provers and verifier. The provers attempt to convince the verifier of the answer to some computational problem. (to converge to a solution?)

Computational Complexity: Studies hardness of a particular computational problem. Formalized in terms of resources required by a deterministic Turing Machine. To consider:
- Considered Models: deterministic, non-deterministic , probabilistic.
- Resources: time, space
- Interaction among models of different abilities. (example? Many interesting relationships among models and resource constraints are known. One common feature is that they are physically motivated.
An example is the class of 
Polynomial Time Computable Functions. It is a mathematical abstraction of a class of functions that can be efficiently computed without errors, on a physical quantum device.)

This train of thought motivates us to think that complexity theory (and computation) are motivated by physical theories; and Quantum Mechanics is a viable candidate for the same.
Why Quantum Mechanics: VLSI feature size is ⬇️, limit is the atomic scale. At atomic scales, quantum phenomena becomes relevant.

How Quantum Mechanics affects complexity theory: Initial definitions laid down by Bernstein and Vazirani (Quantum Complexity Theory[Bernstein-Vazirani1][Bernstein-VaziraniV2]). Shor's Algorithm [Shor1] sheds light into differences in computational hardness notion in classical and quantum subroutines. Another area of quantum complexity-theoretic application: Efficient verification of Quantum proofs (2018 result by Urmila Mahadev↗ is an important result).

Quantum Complexity Theory studies:
- implications of quantum physics to computational complexity theory.
- hardness of computational problems with respect to models of quantum computation.
- how to classify the 'computational problems' based on these models. (the complexity will be different for different models of computation. The models, here, means the models of computation, right? The physical motivation factor, if considered, would it imply that complexity for different qubit-realization technology would differ (even though the model of computation is same)? Speaking of which, quantum computing has 2 models for computation, right? - the circuit model and the adiabatic model? Is topological quantum computing a different model?)

These are complete notes based on:
John Watrous' article, Quantum Computational Complexity (2008)
arXiv: 0804.3401v1

Up Next:
Part 2: Quantum Complexity Classes and Quantum Circuit Model
Part 3: Polynomial Time Quantum Computations
Part 4: Quantum Proofs
Part 5: Quantum Interactive Proof Systems
Part 6: Further Topics: Quantum Advice, Space Bound Quantum Computation, Bounded Depth Quantum Circuits