Note: Often in complexity study, I found the term

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.

A collection of problems that can be solved by

E.g.

The complexity class QMA is defined by this notion.

- 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

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

Why Quantum Mechanics: VLSI feature size is ⬇️, limit is the atomic scale. At atomic scales, quantum phenomena becomes relevant.

- 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

**'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