Quantum complexity theory

Short description: Computational complexity of quantum algorithms

This article includes a list of references, but its sources remain unclear because it has insufficient inline citations. Please help to improve this article by introducing more precise citations. (March 2020) (Learn how and when to remove this template message)

|

Quantum complexity theory is the subfield of computational complexity theory that deals with complexity classes defined using quantum computers, a computational model based on quantum mechanics. It studies the hardness of computational problems in relation to these complexity classes, as well as the relationship between quantum complexity classes and classical (i.e., non-quantum) complexity classes.

Two important quantum complexity classes are BQP and QMA.

## Contents

* 1 Background
* 2 Overview of complexity classes
* 3 BQP
* 4 Simulation of quantum circuits
* 5 Quantum query complexity
* 5.1 Query models of directed graphs
* 5.1.1 Adjacency matrix model
* 5.1.2 Adjacency array model
* 5.2 Quantum query complexity of certain types of graph problems
* 5.3 Other types of quantum computational queries
* 5.3.1 Grover's algorithm
* 5.3.2 Deutsch–Jozsa algorithm
* 6 Other theories of quantum physics
* 7 See also
* 8 Notes
* 9 References
* 10 External links

## Background

See also: Computational complexity and Complexity class

A complexity class is a collection of computational problems that can be solved by a computational model under certain resource constraints. For instance, the complexity class P is defined as the set of problems solvable by a (deterministic) Turing machine in polynomial time. Similarly, quantum complexity classes may be defined using quantum models of computation, such as the quantum circuit model or the equivalent quantum Turing machine. One of the main aims of quantum complexity theory is to find out how these classes relate to classical complexity classes such as P, NP, BPP, and PSPACE.

One of the reasons quantum complexity theory is studied are the implications of quantum computing for the modern Church–Turing thesis. In short the modern Church–Turing thesis states that any computational model can be simulated in polynomial time with a probabilistic Turing machine.[1][2] However, questions around the Church–Turing thesis arise in the context of quantum computing. It is unclear whether the Church–Turing thesis holds for the quantum computation model. There is much evidence that the thesis does not hold. It may not be possible for a probabilistic Turing machine to simulate quantum computation models in polynomial time.[1]

Asymptotic computational complexities of both quantum algorithms and classical algorithms are often expressed with asymptotic notation. Some common forms of asymptotic notation of functions are O(T(n)), Ω(T(n)), and Θ(T(n)). O(T(n)) expresses that something is bounded above by cT(n) where c is a constant such that c>0 and T(n) is a function of n, Ω(T(n)) expresses that something is bounded below by cT(n) where c is a constant such that c>0 and T(n) is a function of n, and Θ(T(n)) expresses both O(T(n)) and Ω(T(n)).[3] These notations also have their own names. O(T(n)) is called big O notation, Ω(T(n)) is called big Omega notation, and Θ(T(n)) is called big Theta notation.

## Overview of complexity classes

The important complexity classes P, BPP, BQP, PP, and PSPACE can be compared based on promise problems. A promise problem is a decision problem that has an input assumed to be selected from the set of all possible input strings. A promise problem is a pair A=(Ayes,Ano), where Ayes is the set of yes instances and Ano is the set of no instances, and the intersection of these sets is empty: Ayes∩Ano=∅. All of the previous complexity classes contain promise problems.[4]

Complexity Class  | Criteria

|

P  | Promise problems for which a polynomial-time deterministic Turing machine accepts all strings in Ayes and rejects all strings in Ano[4]
BPP  | Promise problems for which a polynomial-time probabilistic Turing machine accepts every string in Ayes with a probability of at least 23, and accepts every string in Ano with a probability of at most 13[4]
BQP  | Promise problems such that for functions a,b:ℕ->[0,1], there exists a polynomial-time generated family of quantum circuits Q={Qn:n∈ℕ}, where Qn is a circuit that accepts n qubits and gives an output of one qubit. An element x of Ayes is accepted by Q with a probability greater than or equal to a(|x|). An element x of Ano is accepted by Q with a probability less than or equal to b(|x|).[4]
PP  | Promise problems for which a polynomial-time probabilistic Turing machine accepts every string in Ayes with a probability greater than 12, and accepts every string in Ano with a probability of at most 12[4]
PSPACE  | Promise problems for which a deterministic Turing machine that runs in polynomial space, accepts every string in Ayes and rejects all strings in Ano[4]

## BQP

Main article: BQP

BQP algorithm (1 run)

Answer

produced

Correct
answer

| Yes  | No

|
|

Yes  | ≥ 2/3  | ≤ 1/3
No  | ≤ 1/3  | ≥ 2/3
The suspected relationship of BQP to other complexity classes[5]

The class of problems that can be efficiently solved by a quantum computer with bounded error is called BQP ("bounded error, quantum, polynomial time"). More formally, BQP is the class of problems that can be solved by a polynomial-time quantum Turing machine with error probability of at most 1/3.

As a class of probabilistic problems, BQP is the quantum counterpart to BPP ("bounded error, probabilistic, polynomial time"), the class of problems that can be efficiently solved by probabilistic Turing machines with bounded error.[6] It is known that BPP⊆BQP and widely suspected, but not proven, that BQP⊈BPP, which intuitively would mean that quantum computers are more powerful than classical computers in terms of time complexity.[7] BQP is a subset of PP.

The exact relationship of BQP to P, NP, and PSPACE is not known. However, it is known that P⊆BQP⊆PSPACE; that is, the class of problems that can be efficiently solved by quantum computers includes all problems that can be efficiently solved by deterministic classical computers but does not include any problems that cannot be solved by classical computers with polynomial space resources. It is further suspected that BQP is a strict superset of P, meaning there are problems that are efficiently solvable by quantum computers that are not efficiently solvable by deterministic classical computers. For instance, integer factorization and the discrete logarithm problem are known to be in BQP and are suspected to be outside of P. On the relationship of BQP to NP, little is known beyond the fact that some NP problems are in BQP (integer factorization and the discrete logarithm problem are both in NP, for example). It is suspected that NP⊈BQP; that is, it is believed that there are efficiently checkable problems that are not efficiently solvable by a quantum computer. As a direct consequence of this belief, it is also suspected that BQP is disjoint from the class of NP-complete problems (if any NP-complete problem were in BQP, then it follows from NP-hardness that all problems in NP are in BQP).[8]

The relationship of BQP to the essential classical complexity classes can be summarized as:

P⊆BPP⊆BQP⊆PP⊆PSPACE

It is also known that BQP is contained in the complexity class #P (or more precisely in the associated class of decision problems P#P),[8] which is a subset of PSPACE.

## Simulation of quantum circuits

There is no known way to efficiently simulate a quantum computational model with a classical computer. This means that a classical computer cannot simulate a quantum computational model in polynomial time. However, a quantum circuit of S(n) qubits with T(n) quantum gates can be simulated by a classical circuit with O(2S(n)T(n)3) classical gates.[3] This number of classical gates is obtained by determining how many bit operations are necessary to simulate the quantum circuit. In order to do this, first the amplitudes associated with the S(n) qubits must be accounted for. Each of the states of the S(n) qubits can be described by a two-dimensional complex vector, or a state vector. These state vectors can also be described a linear combination of its component vectors with coefficients called amplitudes. These amplitudes are complex numbers that are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one.[3] The entries of the state vector are these amplitudes. The amplitudes, acting as coefficients in the linear combination description, each correspond to a non-zero component of the state vector. As an equation this is described as α[10]+β[01]=[αβ] or α|1⟩+β|0⟩=[αβ] using Dirac notation. The state of the entire S(n) qubit system can be described by a single state vector. This state vector describing the entire system is the tensor product of the state vectors describing the individual qubits in the system. The result of the tensor products of the S(n) qubits is a single state vector that has 2S(n) dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, 2S(n)amplitudes must be accounted for with a 2S(n) dimensional complex vector, which is the state vector for the S(n) qubit system.[9] In order to obtain an upper bound for the number of gates required to simulate a quantum circuit we need a sufficient upper bound for the amount data used to specify the information about each of the 2S(n) amplitudes. To do this O(T(n)) bits of precision are sufficient for encoding each amplitude.[3] So it takes O(2S(n)T(n)) classical bits to account for the state vector of the S(n) qubit system. Next the application of the T(n) quantum gates on 2S(n) amplitudes must be accounted for. The quantum gates can be represented as 2S(n)×2S(n) sparse matrices.[3] So to account for the application of each of the T(n) quantum gates, the state vector must be multiplied by a 2S(n)×2S(n) sparse matrix for each of the T(n) quantum gates. Every time the state vector is multiplied by a 2S(n)×2S(n) sparse matrix, O(2S(n)) arithmetic operations must be performed.[3] Therefore, there are O(2S(n)T(n)2) bit operations for every quantum gate applied to the state vector. So O(2S(n)T(n)2) classical gate are needed to simulate S(n) qubit circuit with just one quantum gate. Therefore, O(2S(n)T(n)3) classical gates are needed to simulate a quantum circuit of S(n) qubits with T(n) quantum gates.[3] While there is no known way to efficiently simulate a quantum computer with a classical computer, it is possible to efficiently simulate a classical computer with a quantum computer. This is evident from the fact that BPP⊆BQP.[4]

## Quantum query complexity

One major advantage of using a quantum computational system instead of a classical one, is that a quantum computer may be able to give a polynomial-time algorithm for some problem for which no classical polynomial-time algorithm exists, but more importantly, a quantum computer may significantly decrease the calculation time for a problem that a classical computer can already solve efficiently. Essentially, a quantum computer may be able to both determine how long it will take to solve a problem, while a classical computer may be unable to do so, and can also greatly improve the computational efficiency associated with the solution to a particular problem. Quantum query complexity refers to how complex, or how many queries to the graph associated with the solution of a particular problem, are required to solve the problem. Before we delve further into query complexity, let us consider some background regarding graphing solutions to particular problems, and the queries associated with these solutions.

### Query models of directed graphs

One type of problem that quantum computing can make easier to solve are graph problems. If we are to consider the amount of queries to a graph that are required to solve a given problem, let us first consider the most common types of graphs, called directed graphs, that are associated with this type of computational modelling. In brief, directed graphs are graphs where all edges between vertices are unidirectional. Directed graphs are formally defined as the graph G=(N,E), where N is the set of vertices, or nodes, and E is the set of edges.[10]

#### Adjacency matrix model

When considering quantum computation of the solution to directed graph problems, there are two important query models to understand. First, there is the adjacency matrix model, where the graph of the solution is given by the adjacency matrix: M∈{0,1}anXn, with Mij=1, if and only if (vi,vj)∈E.[11]

#### Adjacency array model

Next, there is the slightly more complicated adjacency array model built on the idea of adjacency lists, where every vertex, u, is associated with an array of neighboring vertices such that fi:[di+]->[n], for the out-degrees of vertices di+,...,dn+, where n is the minimum value of the upper bound of this model, and fi(j) returns the "jth" vertex adjacent to i. Additionally, the adjacency array model satisfies the simple graph condition, ∀i∈[n],j,j′∈[k],j≠j′:fi(j)≠fi(j′), meaning that there is only one edge between any pair of vertices, and the number of edges is minimized throughout the entire model (see Spanning tree model for more background).[11]

### Quantum query complexity of certain types of graph problems

Both of the above models can be used to determine the query complexity of particular types of graphing problems, including the connectivity, strong connectivity (a directed graph version of the connectivity model), minimum spanning tree, and single source shortest path models of graphs. An important caveat to consider is that the quantum complexity of a particular type of graphing problem can change based on the query model (namely either matrix or array) used to determine the solution. The following table showing the quantum query complexities of these types of graphing problems illustrates this point well.

Quantum query complexity of certain types of graph problems  Problem  | Matrix model  | Array model

|
|

Minimum spanning tree  | Θ(n3/2) | Θ(nm)
Connectivity  | Θ(n3/2) | Θ(n)
Strong connectivity  | Θ(n3/2) | Ω(nm), O(nmlog⁡(n))
Single source shortest path  | Ω(n3/2), O(n3/2log2n) | Ω(nm), O(nmlog2(n))

Notice the discrepancy between the quantum query complexities associated with a particular type of problem, depending on which query model was used to determine the complexity. For example, when the matrix model is used, the quantum complexity of the connectivity model in big O notation is Θ(n3/2), but when the array model is used, the complexity is Θ(n). Additionally, for brevity, we use the shorthand m in certain cases, where m=Θ(n2).[11] The important implication here is that the efficiency of the algorithm used to solve a graphing problem is dependent on the type of query model used to model the graph.

### Other types of quantum computational queries

In the query complexity model, the input can also be given as an oracle (black box). The algorithm gets information about the input only by querying the oracle. The algorithm starts in some fixed quantum state and the state evolves as it queries the oracle.

Similar to the case of graphing problems, the quantum query complexity of a black-box problem is the smallest number of queries to the oracle that are required in order to calculate the function. This makes the quantum query complexity a lower bound on the overall time complexity of a function.

#### Grover's algorithm

An example depicting the power of quantum computing is Grover's algorithm for searching unstructured databases. The algorithm's quantum query complexity is O(N), a quadratic improvement over the best possible classical query complexity O(N), which is a linear search. Grover's algorithm is asymptotically optimal; in fact, it uses at most a 1+o(1) fraction more queries than the best possible algorithm.[12]

#### Deutsch–Jozsa algorithm

The Deutsch–Jozsa algorithm is a quantum algorithm designed to solve a toy problem with a smaller query complexity than is possible with a classical algorithm. The toy problem asks whether a function f:{0,1}n->{0,1} is constant or balanced, those being the only two possibilities.[2] The only way to evaluate the function f is to consult a black box or oracle. A classical deterministic algorithm will have to check more than half of the possible inputs to be sure of whether or not the function is constant or balanced. With 2n possible inputs, the query complexity of the most efficient classical deterministic algorithm is 2n−1+1.[2] The Deutsch–Jozsa algorithm takes advantage of quantum parallelism to check all of the elements of the domain at once and only needs to query the oracle once, making its query complexity 1.[2]

## Other theories of quantum physics

It has been speculated that further advances in physics could lead to even faster computers. For instance, it has been shown that a non-local, but non-signaling hidden variable quantum computer could implement a search of an N-item database in at most O(N3) steps, a slight speedup over Grover's algorithm, which runs in O(N) steps. Note, however, that neither search method would allow quantum computers to solve NP-complete problems in polynomial time.[13] Theories of quantum gravity, such as M-theory and loop quantum gravity, may allow even faster computers to be built. However, defining computation in these theories is an open problem due to the problem of time; that is, within these physical theories there is currently no obvious way to describe what it means for an observer to submit input to a computer at one point in time and then receive output at a later point in time.[14][15]

## See also

* Quantum computing
* Quantum Turing machine
* Polynomial hierarchy (PH)

## Notes

1. ↑ 1.0 1.1 Vazirani, Umesh V. (2002). "A survey of quantum complexity theory". Quantum Computation. Proceedings of Symposia in Applied Mathematics. 58. pp. 193–217. doi:10.1090/psapm/058/1922899. ISBN 9780821820841.
2. ↑ 2.0 2.1 2.2 2.3 Nielsen, Michael A., 1974- (2010). Quantum computation and quantum information. Chuang, Isaac L., 1968- (10th anniversary ed.). Cambridge: Cambridge University Press. ISBN 978-1-107-00217-3. OCLC 665137861.
3. ↑ 3.0 3.1 3.2 3.3 3.4 3.5 3.6 Cleve, Richard (2000), "An Introduction to Quantum Complexity Theory", Quantum Computation and Quantum Information Theory (WORLD SCIENTIFIC): pp. 103–127, doi:10.1142/9789810248185_0004, ISBN 978-981-02-4117-9, Bibcode: 2000qcqi.book..103C, http://dx.doi.org/10.1142/9789810248185_0004, retrieved October 10, 2020
4. ↑ 4.0 4.1 4.2 4.3 4.4 4.5 4.6 Watrous, John (2008-04-21). "Quantum Computational Complexity". arXiv:0804.3401 [quant-ph].
5. ↑ Nielsen, p. 42
6. ↑ Nielsen, Michael; Chuang, Isaac (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. p. 41. ISBN 978-0-521-63503-5. OCLC 174527496. https://books.google.com/books?id=aai-P4V9GJ8C.
7. ↑ Nielsen, p. 201
8. ↑ 8.0 8.1 Bernstein, Ethan; Vazirani, Umesh (1997). "Quantum Complexity Theory". SIAM Journal on Computing 26 (5): 1411–1473. doi:10.1137/S0097539796300921. http://www.cs.berkeley.edu/~vazirani/bv.ps.
9. ↑ Häner, Thomas; Steiger, Damian S. (2017-11-12). "0.5 petabyte simulation of a 45-qubit quantum circuit". Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. New York, NY, USA: ACM. pp. 1–10. doi:10.1145/3126908.3126947. ISBN 978-1-4503-5114-0. http://dx.doi.org/10.1145/3126908.3126947.
10. ↑ Nykamp, D.Q.. "Directed Graph Definition". https://mathinsight.org/definition/directed_graph.
11. ↑ 11.0 11.1 11.2 Durr, Christoph; Heiligman, Mark; Hoyer, Peter; Mhalla, Mehdi (January 2006). "Quantum query complexity of some graph problems". SIAM Journal on Computing 35 (6): 1310–1328. doi:10.1137/050644719. ISSN 0097-5397.
12. ↑ Zalka, Christof (1999-10-01). "Grover's quantum searching algorithm is optimal". Physical Review A 60 (4): 2746–2751. doi:10.1103/PhysRevA.60.2746. Bibcode: 1999PhRvA..60.2746Z. https://link.aps.org/doi/10.1103/PhysRevA.60.2746.
13. ↑ Aaronson, Scott (2005). "Quantum Computing and Hidden Variables". Phys. Rev. A 71 (3). doi:10.1103/PhysRevA.71.032325. http://www.scottaaronson.com/papers/qchvpra.pdf.
14. ↑ Aaronson, Scott (2005). "NP-complete Problems and Physical Reality". ACM SIGACT News 2005. Bibcode: 2005quant.ph..2072A. See section 7 "Quantum Gravity": "[...] to anyone who wants a test or benchmark for a favorite quantum gravity theory,[author's footnote: That is, one without all the bother of making numerical predictions and comparing them to observation] let me humbly propose the following: can you define Quantum Gravity Polynomial-Time? [...] until we can say what it means for a 'user' to specify an 'input' and 'later' receive an 'output'—there is no such thing as computation, not even theoretically." (emphasis in original)
15. ↑ "D-Wave Systems sells its first Quantum Computing System to Lockheed Martin Corporation". D-Wave. 25 May 2011. http://www.dwavesys.com/en/pressreleases.html#lm_2011.

## References

* Nielsen, Michael; Chuang, Isaac (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 978-0-521-63503-5. OCLC 174527496.
* Arora, Sanjeev; Barak, Boaz (2016). Computational Complexity: A Modern Approach. Cambridge University Press. pp. 201–236. ISBN 978-0-521-42426-4. https://archive.org/details/computationalcom00aror.
* Watrous, John (2008). "Quantum Computational Complexity". arXiv:0804.3401v1 [quant-ph].
* Watrous J. (2009) Quantum Computational Complexity. In: Meyers R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY

## External links

* MIT lectures by Scott Aaronson

* v
* t
* e

Quantum information science

General|

* Quantum computing
* Qubit
* physical vs. logical
* DiVincenzo's criteria
* Quantum information
* Quantum programming
* Quantum processors
* Cloud-based quantum computing
* Timeline of quantum computing

Theorems|

* Bell's theorem
* Gleason's theorem
* Gottesman–Knill theorem
* Holevo's theorem
* Margolus–Levitin theorem
* No-broadcast theorem
* No-cloning theorem
* No-communication theorem
* No-deleting theorem
* No-hiding theorem
* No-teleportation theorem
* PBR theorem
* Quantum threshold theorem

Quantum
communication|

* Quantum capacity
* Classical capacity
* Entanglement-assisted classical capacity
* Quantum channel
* Quantum network
* Quantum cryptography
* Quantum key distribution
* BB84
* SARG04
* Three-stage quantum cryptography protocol
* Quantum teleportation
* Superdense coding
* LOCC
* Entanglement distillation

Quantum algorithms|

* Universal quantum simulator
* Deutsch–Jozsa algorithm
* Grover's algorithm
* Quantum Fourier transform
* Shor's algorithm
* Simon's problem
* Quantum phase estimation algorithm
* Quantum counting algorithm
* Quantum annealing
* Quantum algorithm for linear systems of equations
* Amplitude amplification

Quantum
complexity theory|

* Quantum Turing machine
* EQP
* BQP
* QMA
* PostBQP
* QIP

Quantum
computing models|

* Quantum circuit
* Quantum logic gate
* One-way quantum computer
* cluster state
* Adiabatic quantum computation
* Topological quantum computer

Quantum
error correction|

* Stabilizer codes
* Entanglement-Assisted Quantum Error Correction
* Shor code
* Steane code
* CSS code
* Quantum convolutional codes
* Toric code

Physical
implementations|

| Quantum optics|

* Cavity QED
* Circuit QED
* Linear optical quantum computing
* KLM protocol
* Boson sampling

|

Ultracold atoms|

* Trapped ion quantum computer
* Optical lattice

Spin-based|

* Nuclear magnetic resonance QC
* Kane QC
* Loss–DiVincenzo QC
* Nitrogen-vacancy center

Superconducting
quantum computing|

* Charge qubit
* Flux qubit
* Phase qubit
* Transmon

Software|

* libquantum
* OpenQASM
* Q#
* Qiskit
* IBM Q Experience

* v
* t
* e

Quantum mechanics

Background|

* Introduction
* History
* timeline
* Glossary
* Classical mechanics
* Old quantum theory

Fundamentals|

* Bra–ket notation
* Casimir effect
* Complementarity
* Density matrix
* Energy level
* ground state
* excited state
* degenerate levels
* Vacuum state
* Zero-point energy
* QED vacuum
* QCD vacuum
* Hamiltonian
* Operator
* Quantum coherence
* Quantum decoherence
* Measurement
* Quantum
* Quantum realm
* Quantum system
* Quantum state
* Quantum number
* Quantum entanglement
* Quantum superposition
* Quantum nonlocality
* Quantum tunnelling
* Quantum levitation
* Quantum fluctuation
* Quantum annealing
* Quantum foam
* Quantum noise
* Heisenberg uncertainty principle
* Spontaneous parametric down-conversion
* Von Neumann entropy
* Spin
* Scattering theory
* Symmetry in quantum mechanics
* Symmetry breaking
* Spontaneous symmetry breaking
* Wave propagation
* Quantum interference
* Wave function
* Wave function collapse
* Wave–particle duality
* Matter wave
* Qubit
* Qutrit
* Observable
* Probability distribution

Formulations|

* Formulations
* Heisenberg
* Interaction
* Matrix mechanics
* Schrödinger
* Path integral formulation
* Phase space

Equations|

* Dirac
* Klein–Gordon
* Pauli
* Rydberg
* Schrödinger

Interpretations|

* Interpretations
* Bayesian
* Consistent histories
* Copenhagen
* de Broglie–Bohm
* Ensemble
* Hidden variables
* Many worlds
* Objective collapse
* Quantum logic
* Relational
* Stochastic
* Transactional
* Cosmological

Experiments|

* Afshar
* Bell's inequality
* Cold Atom Laboratory
* Davisson–Germer
* Delayed-choice quantum eraser
* Double-slit
* Franck–Hertz experiment
* Leggett–Garg inequality
* Mach-Zehnder inter.
* Elitzur–Vaidman
* Popper
* Quantum eraser
* Schrödinger's cat
* Quantum suicide and immortality
* Stern–Gerlach
* Wheeler's delayed choice

Science|

* Q-analog
* List
* Quantum algebra
* Quantum calculus
* Quantum differential calculus
* Quantum geometry
* Quantum group
* Quantum Bayesianism
* Quantum biology
* Quantum chemistry
* Quantum chaos
* Quantum cognition
* Quantum cosmology
* Quantum dynamics
* Quantum economics
* Quantum evolution
* Quantum finance
* Quantum game theory
* Quantum measurement problem
* Quantum mind
* Quantum probability
* Quantum social science
* Quantum stochastic calculus
* Quantum spacetime

Technology|

* Quantum algorithms
* Quantum amplifier
* Quantum cellular automata
* Quantum finite automata
* Quantum electronics
* Quantum logic gates
* Quantum clock
* Quantum channel
* Quantum bus
* Quantum circuit
* Phase qubit
* Matrix isolation
* Quantum dot
* Quantum dot display
* Quantum dot solar cell
* Quantum dot cellular automaton
* Quantum dot single-photon source
* Quantum dot laser
* Quantum well
* Quantum computing
* Timeline
* Quantum cryptography
* Post-quantum cryptography
* Quantum error correction
* Quantum imaging
* Quantum image processing
* Quantum information
* Quantum key distribution
* Quantum machine
* Quantum machine learning
* Quantum metamaterial
* Quantum metrology
* Quantum network
* Quantum neural network
* Quantum optics
* Quantum programming
* Quantum sensors
* Quantum simulator
* Quantum teleportation
* Quantum levitation
* Time travel
* Quantum complexity theory

Extensions|

* Quantum statistical mechanics
* Relativistic quantum mechanics
* Quantum field theory
* Axiomatic quantum field theory
* Quantum field theory in curved spacetime
* Thermal quantum field theory
* Topological quantum field theory
* Local quantum field theory
* Conformal field theory
* Two-dimensional conformal field theory
* Liouville field theory
* History
* Quantum gravity

* Category
* Physics Portal
* Physics WikiProject
* Commons

* v
* t
* e

Emerging technologies

Fields|

| Agriculture|

* Agricultural robot
* Cellular agriculture
* Closed ecological systems
* Cultured meat
* Genetically modified food
* Precision agriculture
* Vertical farming

|

Architecture|

* Arcology
* Building printing
* Contour crafting
* Domed city

Biomedical|

* Artificial uterus
* Ampakine
* Brain transplant
* Cryonics
* Cryoprotectant
* Cryopreservation
* Vitrification
* Suspended animation
* De-extinction
* Genetic engineering
* Gene therapy
* Head transplant
* Isolated brain
* Life extension
* Strategies for Engineered Negligible Senescence
* Nanomedicine
* Nanosensors
* Organ printing
* Personalized medicine
* Regenerative medicine
* Stem-cell therapy
* Tissue engineering
* Robot-assisted surgery
* Synthetic biology
* Synthetic genomics
* Virotherapy
* Oncolytic virus
* Tricorder
* Whole genome sequencing

Displays|

| Next generation|

* FED
* FLCD
* iMoD
* Laser
* LPD
* OLED
* OLET
* QD-LED
* SED
* TPD
* TDEL
* TMOS
* MicroLED

|

Screenless|

* Bionic contact lens
* Head-mounted display
* Head-up display
* Optical head-mounted display
* Virtual retinal display

Other|

* Autostereoscopy
* Flexible display
* Holographic display
* Computer-generated holography
* Multi-primary color display
* Ultra HD
* Volumetric display

Electronics|

* Electronic nose
* E-textiles
* Flexible electronics
* Molecular electronics
* Nanoelectromechanical systems
* Memristor
* Spintronics
* Thermal copper pillar bump
* Twistronics

Energy|

| Production|

* Airborne wind turbine
* Artificial photosynthesis
* Biofuels
* Carbon-neutral fuel
* Concentrated solar power
* Fusion power
* Home fuel cell
* Hydrogen economy
* Methanol economy
* Molten salt reactor
* Nantenna
* Photovoltaic pavement
* Space-based solar power
* Vortex engine

|

Storage|

* Beltway battery
* Compressed air energy storage
* Flywheel energy storage
* Grid energy storage
* Lithium–air battery
* Molten-salt battery
* Nanowire battery
* Research in lithium-ion batteries
* Silicon–air battery
* Thermal energy storage
* Ultracapacitor

Other|

* Smart grid
* Wireless power

Information and
communications

* Ambient intelligence
* Internet of things
* Artificial intelligence
* Applications of artificial intelligence
* Progress in artificial intelligence
* Machine translation
* Mobile translation
* Machine vision
* Semantic Web
* Speech recognition
* Atomtronics
* Carbon nanotube field-effect transistor
* Cybermethodology
* Fourth-generation optical discs
* 3D optical data storage
* Holographic data storage
* GPGPU
* Memory
* CBRAM
* FRAM
* Millipede
* MRAM
* NRAM
* PRAM
* Racetrack memory
* RRAM
* SONOS
* Optical computing
* RFID
* Chipless RFID
* Software-defined radio
* Three-dimensional integrated circuit

Manufacturing|

* 3D printing
* Claytronics
* Molecular assembler
* Utility fog

Materials science|

* Aerogel
* Amorphous metal
* Artificial muscle
* Conductive polymer
* Femtotechnology
* Fullerene
* Graphene
* High-temperature superconductivity
* High-temperature superfluidity
* Linear acetylenic carbon
* Metamaterials
* Metamaterial cloaking
* Metal foam
* Multi-function structures
* Nanotechnology
* Carbon nanotubes
* Molecular nanotechnology
* Nanomaterials
* Picotechnology
* Programmable matter
* Quantum dots
* Silicene
* Superalloy
* Synthetic diamond

Military|

* Antimatter weapon
* Caseless ammunition
* Directed-energy weapon
* Laser
* Maser
* Particle-beam weapon
* Sonic weapon
* Coilgun
* Railgun
* Plasma weapon
* Pure fusion weapon
* Stealth technology
* Vortex ring gun

Neuroscience|

* Artificial brain
* Brain–computer interface
* Electroencephalography
* Mind uploading
* Brain-reading
* Neuroinformatics
* Neuroprosthetics
* Bionic eye
* Brain implant
* Exocortex
* Retinal implant

Quantum|

* Quantum algorithms
* Quantum amplifier
* Quantum bus
* Quantum channel
* Quantum circuit
* Quantum complexity theory
* Quantum computing
* Quantum cryptography
* Quantum dynamics
* Quantum electronics
* Quantum error correction
* Quantum imaging
* Quantum information
* Quantum key distribution
* Quantum logic
* Quantum logic gates
* Quantum machine
* Quantum machine learning
* Quantum metamaterial
* Quantum metrology
* Quantum network
* Quantum neural network
* Quantum optics
* Quantum programming
* Quantum sensing
* Quantum simulator
* Quantum teleportation

Robotics|

* Domotics
* Nanorobotics
* Powered exoskeleton
* Self-reconfiguring modular robot
* Swarm robotics
* Uncrewed vehicle

Space science|

| Launch|

* Fusion rocket
* Non-rocket spacelaunch
* Mass driver
* Orbital ring
* Skyhook
* Space elevator
* Space fountain
* Space tether
* Reusable launch system

|

Propulsion|

* Beam-powered propulsion
* Ion thruster
* Laser propulsion
* Plasma propulsion engine
* Helicon thruster
* VASIMR
* Nuclear pulse propulsion
* Solar sail

Other|

* Interstellar travel
* Propellant depot
* Laser communication in space

Transport|

| Aerial|

* Adaptive compliant wing
* Backpack helicopter
* Delivery drone
* Flying car
* High-altitude platform
* Jet pack
* Pulse detonation engine
* Scramjet
* Spaceplane
* Supersonic transport

|

Land|

* Airless tire
* Alternative fuel vehicle
* Hydrogen vehicle
* Driverless car
* Ground effect train
* Hyperloop
* Maglev train
* Personal rapid transit
* Transit Elevated Bus
* Vactrain
* Vehicular communication systems

Pipeline|

* Pneumatic transport
* Automated vacuum collection

Other|

* Anti-gravity
* Cloak of invisibility
* Digital scent technology
* Force field
* Plasma window
* Immersive virtual reality
* Magnetic refrigeration
* Phased-array optics

Topics|

* Collingridge dilemma
* Differential technological development
* Disruptive Innovation
* Ephemeralization
* Exploratory engineering
* Fictional technology
* Proactionary principle
* Technological change
* Technological unemployment
* Technological convergence
* Technological evolution
* Technological paradigm
* Technology forecasting
* Accelerating change
* Moore's law
* Technological singularity
* Technology scouting
* Technology readiness level
* Technology roadmap
* Transhumanism

* Category
* List

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Quantum complexity theory. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Quantum_complexity_theory&oldid=4229643"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template