Quantum complexity theory — Safekipedia Discoverer

Quantum complexity theory is a fascinating area of science that explores how hard certain problems are to solve using special computers called quantum computers. Unlike regular computers that use bits, which can be either 0 or 1, quantum computers use tiny particles called qubits that can be both 0 and 1 at the same time thanks to the rules of quantum mechanics. This special ability lets quantum computers solve some problems much faster.

This field of study looks at how different types of problems behave when tackled with quantum computers. It examines groups of problems, known as complexity classes, to understand their difficulty levels. One important class is called BQP, which includes problems that quantum computers can solve efficiently. Another class, QMA, helps us understand problems for which proving a solution is easy if you have the right evidence.

By studying these classes, scientists can compare the power of quantum computers to regular computers and discover what kinds of problems each can solve better. This research helps us understand the limits and possibilities of computing in the future, opening new doors to solving complex puzzles that were once thought impossible.

Background

A complexity class is a group of problems that can be solved by computers with certain limits on time or resources. For example, the class P includes problems that can be solved quickly by a regular computer. Quantum complexity theory looks at problems that can be solved by quantum computers, which use the rules of quantum physics. It studies how these quantum problems relate to classic problems.

One big question in this area is whether quantum computers can do things that regular computers cannot. This ties into a idea called the Church–Turing thesis, which says that any computer, given enough time, can simulate any other computer. But with quantum computers, we are not sure if this still holds true. Some think quantum computers might be able to solve certain problems much faster than regular ones. To talk about how fast problems are solved, scientists use special math words like big O notation, which helps describe the speed of algorithms.

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 where the input is assumed to come from a specific set of possible strings. It has two parts: one for "yes" answers and one for "no" answers, and 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 can be solved efficiently by a quantum computer, with a small chance of giving the wrong answer. Quantum computers are different from regular computers because they use the rules of quantum mechanics.

We believe quantum computers might be able to solve some problems faster than regular computers, but we are not sure. For example, problems like breaking certain codes by finding the factors of large numbers seem to be in BQP. However, we also think that not all problems, especially very hard ones, can be solved quickly by quantum computers.

BQP algorithm (1 run)
Answer produced Correct answer	Yes	No
Yes	≥ 2/3	≤ 1/3
No	≤ 1/3	≥ 2/3

Simulation of quantum circuits

There is currently no known way for a regular computer to quickly simulate what a quantum computer can do. This means a regular computer cannot copy a quantum computer's work in a fast, step-by-step way. However, scientists have found that a quantum computer can easily simulate the work of a regular computer.

A quantum circuit with S(n) qubits and T(n) quantum gates can be simulated by a regular computer, but it would need a very large number of steps—specifically, about O(2^{S(n)}T(n)^3) steps. This shows just how much more powerful quantum computers could be for certain tasks.

Quantum query complexity

Quantum computers can solve some problems faster than classical computers. One way to measure this is through quantum query complexity, which looks at 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 determine how long a problem will take to solve, which classical computers might not be able to do. They can also improve how efficiently problems are solved. This is especially useful for problems involving graphs, where 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

Quantum query complexity of certain types of graph problems
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 wonder if new discoveries in physics might lead to even faster computers. For example, some ideas suggest a special type of quantum computer could search through a list of N items in fewer steps than current methods, though it still wouldn’t solve very hard problems quickly. Theories about the very nature of space and time, like M-theory and loop quantum gravity, might also lead to faster computers, but we don’t yet know how to describe how such computers would work because of tricky questions about time itself.