SafekipediaQuantum complexity theory
Adapted from Wikipedia · Adventurer experience
Quantum complexity theory is a cool area of science. It looks at how hard some problems are to solve with special computers called quantum computers.
Regular computers use bits. These bits can be either 0 or 1. Quantum computers use tiny particles called qubits. Because of quantum mechanics, qubits can be both 0 and 1 at the same time. This helps quantum computers solve some problems much faster.
This field of study checks how different problems act when we use quantum computers. It looks at groups of problems, called complexity classes. We study their difficulty levels.
One important class is BQP. It includes problems that quantum computers can solve quickly. Another class is QMA. It helps us understand problems where proving a solution is easy if you have the right proof.
By studying these classes, scientists can compare quantum computers to regular computers. They discover what problems each type can solve better. This research helps us understand what computers can do in the future. It opens new ways to solve tough puzzles that seemed impossible before.
Background
See also: Computational complexity and Complexity class
A complexity class is a group of problems that computers can solve with limits on time or resources. For example, the class P includes problems that regular computers can solve quickly. Quantum complexity theory studies problems that quantum computers can solve. Quantum computers use the rules of quantum physics. This theory looks at how quantum problems relate to classic problems.
One big question is whether quantum computers can do things that regular computers cannot. This relates to an idea called the Church–Turing thesis. This idea says that any computer, given enough time, can simulate any other computer. But with quantum computers, we are not sure if this is still true. Some think quantum computers might solve certain problems much faster than regular ones. Scientists use special math words like big O notation to describe how fast algorithms are.
Overview of complexity classes
The complexity classes P, BPP, BQP, PP, and PSPACE can be compared using special types of problems called promise problems. A promise problem is a decision problem. It is a problem where we know the input will come from a certain group of possible strings. It has two parts: one for "yes" answers and one for "no" answers. These two parts do not overlap. These complexity classes all include such promise problems.
| Complexity Class | Criteria |
|---|---|
| P | Promise problems for which a polynomial-time deterministic Turing machine accepts all strings in A yes {\displaystyle A_{\text{yes}}} and rejects all strings in A no {\displaystyle A_{\text{no}}} |
| BPP | Promise problems for which a polynomial-time probabilistic Turing machine accepts every string in A yes {\displaystyle A_{\text{yes}}} with a probability of at least 2 3 {\displaystyle {\frac {2}{3}}} , and accepts every string in A no {\displaystyle A_{\text{no}}} with a probability of at most 1 3 {\displaystyle {\frac {1}{3}}} |
| BQP | Promise problems such that for functions a , b : N → [ 0 , 1 ] {\displaystyle a,b:\mathbb {N} \to [0,1]} , there exists a polynomial-time generated family of quantum circuits Q = { Q n : n ∈ N } {\displaystyle Q={\{Q_{n}:n\in \mathbb {N} \}}} , where Q n {\displaystyle Q_{n}} is a circuit that accepts n {\displaystyle n} qubits and gives an output of one qubit. An element x {\displaystyle x} of A yes {\displaystyle A_{\text{yes}}} is accepted by Q {\displaystyle Q} with a probability greater than or equal to a ( | x | ) {\displaystyle a(\left\vert x\right\vert )} . An element x {\displaystyle x} of A no {\displaystyle A_{\text{no}}} is accepted by Q {\displaystyle Q} with a probability less than or equal to b ( | x | ) {\displaystyle b(\left\vert x\right\vert )} . |
| PP | Promise problems for which a polynomial-time probabilistic Turing machine accepts every string in A yes {\displaystyle A_{\text{yes}}} with a probability greater than 1 2 {\displaystyle {\frac {1}{2}}} , and accepts every string in A no {\displaystyle A_{\text{no}}} with a probability of at most 1 2 {\displaystyle {\frac {1}{2}}} |
| PSPACE | Promise problems for which a deterministic Turing machine that runs in polynomial space, accepts every string in A yes {\displaystyle A_{\text{yes}}} and rejects all strings in A no {\displaystyle A_{\text{no}}} |
BQP
Main article: BQP
BQP stands for "bounded error, quantum, polynomial time." It describes problems that a quantum computer can solve quickly, but with a small chance of giving the wrong answer. Quantum computers work using the rules of quantum mechanics, which are different from regular computers.
We think quantum computers might solve some problems faster than regular computers, but we are not sure. For example, some problems, like breaking certain codes, might be easier for quantum computers. However, not all problems, especially very hard ones, can be solved quickly by quantum computers.
Answer produced Correct answer | Yes | No |
|---|---|---|
| Yes | ≥ 2/3 | ≤ 1/3 |
| No | ≤ 1/3 | ≥ 2/3 |
Simulation of quantum circuits
Regular computers cannot quickly copy what a quantum computer can do. But quantum computers can easily copy what regular computers do.
A quantum circuit needs many steps for a regular computer to simulate it. This shows quantum computers can be more powerful for some tasks.
Quantum query complexity
Quantum computers can solve some problems faster than regular computers. One way to measure this is through quantum query complexity. This measures how many times a computer needs to check information to solve a problem.
Quantum computers can sometimes solve problems much faster. For example, they can figure out how long a problem will take to solve. Regular computers might not be able to do this. They can also make problem solving more efficient. This is especially helpful for problems with graphs. Quantum computers might need fewer checks to find an answer.
polynomial-time algorithm
directed graphs
adjacency matrix
adjacency lists
Spanning tree
strong connectivity
minimum spanning tree
single source shortest path
big O notation
Grover's algorithm
linear search
asymptotically optimal
Deutsch–Jozsa algorithm
black box
oracle
deterministic algorithm
| Problem | Matrix model | Array model |
|---|---|---|
| Minimum spanning tree | Θ ( n 3 / 2 ) {\displaystyle \Theta (n^{3/2})} | Θ ( n m ) {\displaystyle \Theta ({\sqrt {nm}})} |
| Connectivity | Θ ( n 3 / 2 ) {\displaystyle \Theta (n^{3/2})} | Θ ( n ) {\displaystyle \Theta (n)} |
| Strong connectivity | Θ ( n 3 / 2 ) {\displaystyle \Theta (n^{3/2})} | Ω ( n m ) {\displaystyle \Omega ({\sqrt {nm}})} , O ( n m log ( n ) ) {\displaystyle O({\sqrt {nm\log(n)}})} |
| Single source shortest path | Ω ( n 3 / 2 ) {\displaystyle \Omega (n^{3/2})} , O ( n 3 / 2 log 2 n ) {\displaystyle O(n^{3/2}\log ^{2}n)} | Ω ( n m ) {\displaystyle \Omega ({\sqrt {nm}})} , O ( n m log 2 ( n ) ) {\displaystyle O({\sqrt {nm}}\log ^{2}(n))} |
Other theories of quantum physics
Scientists think new ideas in physics could help make even faster computers. Some ideas suggest a special kind of quantum computer could find something in a list of N items more quickly than regular computers. But it still wouldn’t solve very hard problems fast.
Theories about the nature of space and time, like M-theory and loop quantum gravity, might also help create faster computers. However, we don’t yet know how these computers would work because of tricky questions about time.
Related articles
This article is a child-friendly adaptation of the Wikipedia article on Quantum complexity theory, available under CC BY-SA 4.0.