Quantum simulator

From Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/Quantum_simulator

In this photograph of a quantum simulator crystal the ions are fluorescing, indicating the qubits are all in the same state (either "1" or "0"). Under the right experimental conditions, the ion crystal spontaneously forms this nearly perfect triangular lattice structure. Credit: Britton/NIST

Trapped ion quantum simulator illustration: The heart of the simulator is a two-dimensional crystal of beryllium ions (blue spheres in the graphic); the outermost electron of each ion is a quantum bit (qubit, red arrows). The ions are confined by a large magnetic field in a device called a Penning trap (not shown). Inside the trap the crystal rotates clockwise. Credit: Britton/NIST

Quantum simulators permit the study of a quantum system in a programmable fashion. In this instance, simulators are special purpose devices designed to provide insight about specific physics problems. Quantum simulators may be contrasted with generally programmable "digital" quantum computers, which would be capable of solving a wider class of quantum problems.

A universal quantum simulator is a quantum computer proposed by Yuri Manin in 1980 and Richard Feynman in 1982.

A quantum system of many particles could be simulated by a quantum computer using a number of quantum bits similar to the number of particles in the original system. This has been extended to much larger classes of quantum systems.

Quantum simulators have been realized on a number of experimental platforms, including systems of ultracold quantum gases, polar molecules, trapped ions, photonic systems, quantum dots, and superconducting circuits.

Solving physics problems

Many important problems in physics, especially low-temperature physics and many-body physics, remain poorly understood because the underlying quantum mechanics is vastly complex. Conventional computers, including supercomputers, are inadequate for simulating quantum systems with as few as 30 particles because the dimension of the Hilbert space grows exponentially with particle number. Better computational tools are needed to understand and rationally design materials whose properties are believed to depend on the collective quantum behavior of hundreds of particles. Quantum simulators provide an alternative route to understanding the properties of these systems. These simulators create clean realizations of specific systems of interest, which allows precise realizations of their properties. Precise control over and broad tunability of parameters of the system allows the influence of various parameters to be cleanly disentangled.

Quantum simulators can solve problems which are difficult to simulate on classical computers because they directly exploit quantum properties of real particles. In particular, they exploit a property of quantum mechanics called superposition, wherein a quantum particle is made to be in two distinct states at the same time, for example, aligned and anti-aligned with an external magnetic field. Crucially, simulators also take advantage of a second quantum property called entanglement, allowing the behavior of even physically well separated particles to be correlated.

Recently quantum simulators have been used to obtain time crystals and quantum spin liquids.

Trapped-ion simulators

Ion trap based system forms an ideal setting for simulating interactions in quantum spin models. A trapped-ion simulator, built by a team that included the NIST can engineer and control interactions among hundreds of quantum bits (qubits). Previous endeavors were unable to go beyond 30 quantum bits. The capability of this simulator is 10 times more than previous devices. It has passed a series of important benchmarking tests that indicate a capability to solve problems in material science that are impossible to model on conventional computers.

The trapped-ion simulator consists of a tiny, single-plane crystal of hundreds of beryllium ions, less than 1 millimeter in diameter, hovering inside a device called a Penning trap. The outermost electron of each ion acts as a tiny quantum magnet and is used as a qubit, the quantum equivalent of a “1” or a “0” in a conventional computer. In the benchmarking experiment, physicists used laser beams to cool the ions to near absolute zero. Carefully timed microwave and laser pulses then caused the qubits to interact, mimicking the quantum behavior of materials otherwise very difficult to study in the laboratory. Although the two systems may outwardly appear dissimilar, their behavior is engineered to be mathematically identical. In this way, simulators allow researchers to vary parameters that couldn’t be changed in natural solids, such as atomic lattice spacing and geometry.

Friedenauer et al., adiabatically manipulated 2 spins, showing their separation into ferromagnetic and antiferromagnetic states. Kim et al., extended the trapped ion quantum simulator to 3 spins, with global antiferromagnetic Ising interactions featuring frustration and showing the link between frustration and entanglement and Islam et al., used adiabatic quantum simulation to demonstrate the sharpening of a phase transition between paramagnetic and ferromagnetic ordering as the number of spins increased from 2 to 9. Barreiro et al. created a digital quantum simulator of interacting spins with up to 5 trapped ions by coupling to an open reservoir and Lanyon et al. demonstrated digital quantum simulation with up to 6 ions. Islam, et al., demonstrated adiabatic quantum simulation of the transverse Ising model with variable (long) range interactions with up to 18 trapped ion spins, showing control of the level of spin frustration by adjusting the antiferromagnetic interaction range. Britton, et al. from NIST has experimentally benchmarked Ising interactions in a system of hundreds of qubits for studies of quantum magnetism. Pagano, et al., reported a new cryogenic ion trapping system designed for long time storage of large ion chains demonstrating coherent one and two-qubit operations for chains of up to 44 ions. Joshi, et al., probed the quantum dynamics of 51 individually controlled ions, realizing a long-range interacting spin chain.

Ultracold atom simulators

Many ultracold atom experiments are examples of quantum simulators. These include experiments studying bosons or fermions in optical lattices, the unitary Fermi gas, Rydberg atom arrays in optical tweezers. A common thread for these experiments is the capability of realizing generic Hamiltonians, such as the Hubbard or transverse-field Ising Hamiltonian. Major aims of these experiments include identifying low-temperature phases or tracking out-of-equilibrium dynamics for various models, problems which are theoretically and numerically intractable. Other experiments have realized condensed matter models in regimes which are difficult or impossible to realize with conventional materials, such as the Haldane model and the Harper-Hofstadter model.

Superconducting qubits

Quantum simulators using superconducting qubits fall into two main categories. First, so called quantum annealers determine ground states of certain Hamiltonians after an adiabatic ramp. This approach is sometimes called adiabatic quantum computing. Second, many systems emulate specific Hamiltonians and study their ground state properties, quantum phase transitions, or time dynamics. Several important recent results include the realization of a Mott insulator in a driven-dissipative Bose-Hubbard system and studies of phase transitions in lattices of superconducting resonators coupled to qubits.

Quantum complexity theory

From Wikipedia, the free encyclopedia
https://en.wikipedia.org/wiki/Quantum_complexity_theory

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.

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 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. 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.

Both quantum computational complexity of functions and classical computational complexity of functions are often expressed with asymptotic notation. Some common forms of asymptotic notion of functions are ${\displaystyle O(T(n))}$, ${\displaystyle \mathrm{\Omega }(T(n))}$, and ${\displaystyle \mathrm{\Theta }(T(n))}$. ${\displaystyle O(T(n))}$ expresses that something is bounded above by ${\displaystyle cT(n)}$ where ${\displaystyle c}$ is a constant such that ${\displaystyle c>0}$ and ${\displaystyle T(n)}$ is a function of ${\displaystyle n}$, ${\displaystyle \mathrm{\Omega }(T(n))}$ expresses that something is bounded below by ${\displaystyle cT(n)}$ where ${\displaystyle c}$ is a constant such that ${\displaystyle c>0}$ and ${\displaystyle T(n)}$ is a function of ${\displaystyle n}$, and ${\displaystyle \mathrm{\Theta }(T(n))}$ expresses both ${\displaystyle O(T(n))}$ and ${\displaystyle \mathrm{\Omega }(T(n))}$.^[3] These notations also have their own names. ${\displaystyle O(T(n))}$ is called Big O notation, ${\displaystyle \mathrm{\Omega }(T(n))}$ is called Big Omega notation, and ${\displaystyle \mathrm{\Theta }(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 which has an input assumed to be selected from the set of all possible input strings. A promise problem is a pair ${\displaystyle A=(A_{\text{yes}},A_{\text{no}})}$, where ${\displaystyle A_{\text{yes}}}$ is the set of yes instances and ${\displaystyle A_{\text{no}}}$ is the set of no instances, and the intersection of these sets is empty: ${\displaystyle A_{\text{yes}}\cap A_{\text{no}}=\varnothing }$. All of the previous complexity classes contain promise problems.

Complexity Class	Criteria
P	Promise problems for which a polynomial time deterministic Turing machine accepts all strings in ${\displaystyle A_{\text{yes}}}$ and rejects all strings in ${\displaystyle A_{\text{no}}}$
BPP	Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in ${\displaystyle A_{\text{yes}}}$ with a probability of at least ${\displaystyle \frac{2}{3}}$, and accepts every string in ${\displaystyle A_{\text{no}}}$ with a probability of at most ${\displaystyle \frac{1}{3}}$
BQP	Promise problems such that for functions ${\displaystyle a,b:\mathbb{N}\to [0,1]}$, there exists a polynomial time generated family of quantum circuits ${\displaystyle Q=\{Q_n:n\in \mathbb{N}\}}$, where ${\displaystyle Q_n}$ is a circuit which accepts ${\displaystyle n}$ qubits and gives an output of one qubit. An element ${\displaystyle x}$ of ${\displaystyle A_{\text{yes}}}$ is accepted by ${\displaystyle Q}$ with a probability greater than or equal to ${\displaystyle a(\left|x\right|)}$. An element ${\displaystyle x}$ of ${\displaystyle A_{\text{no}}}$ is accepted by ${\displaystyle Q}$ with a probability less than or equal to ${\displaystyle b(\left|x\right|)}$.
PP	Promise problems for which a polynomial time Probabilistic Turing machine accepts every string in ${\displaystyle A_{\text{yes}}}$ with a probability greater than ${\displaystyle \frac{1}{2}}$, and accepts every string in ${\displaystyle A_{\text{no}}}$ with a probability of at most ${\displaystyle \frac{1}{2}}$
PSPACE	Promise problems for which a deterministic Turing machine, that runs in polynomial space, accepts every string in ${\displaystyle A_{\text{yes}}}$ and rejects all strings in ${\displaystyle A_{\text{no}}}$

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

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. It is known that ${\displaystyle \mathsf{B}\mathsf{P}\mathsf{P}\subseteq \mathsf{B}\mathsf{Q}\mathsf{P}}$ and widely suspected, but not proven, that ${\displaystyle \mathsf{B}\mathsf{Q}\mathsf{P}⊈\mathsf{B}\mathsf{P}\mathsf{P}}$, which intuitively would mean that quantum computers are more powerful than classical computers in terms of time complexity. BQP is a subset of PP.

The exact relationship of BQP to P, NP, and PSPACE is not known. However, it is known that ${\displaystyle \mathsf{P}\subseteq \mathsf{B}\mathsf{Q}\mathsf{P}\subseteq \mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}}$; 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 ${\displaystyle \mathsf{N}\mathsf{P}⊈\mathsf{B}\mathsf{Q}\mathsf{P}}$; 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).

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

${\displaystyle \mathsf{P}\subseteq \mathsf{B}\mathsf{P}\mathsf{P}\subseteq \mathsf{B}\mathsf{Q}\mathsf{P}\subseteq \mathsf{P}\mathsf{P}\subseteq \mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}}$

It is also known that BQP is contained in the complexity class ${\displaystyle \mathsf{\#}\mathsf{P}}$ (or more precisely in the associated class of decision problems ${\displaystyle {\mathsf{P}}^{\mathsf{\#}\mathsf{P}}}$), 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 ${\displaystyle S(n)}$ qubits with ${\displaystyle T(n)}$ quantum gates can be simulated by a classical circuit with ${\displaystyle O(2^{S(n)}T(n{)}^3)}$ classical gates. 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 ${\displaystyle S(n)}$ qubits must be accounted for. Each of the states of the ${\displaystyle 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 which are normalized to one, meaning the sum of the squares of the absolute values of the amplitudes must be one. The entries of the state vector are these amplitudes. Which entry each of the amplitudes are correspond to the none-zero component of the component vector which they are the coefficients of in the linear combination description. As an equation this is described as ${\displaystyle \alpha \left[\begin{array}{c}1\\ 0\end{array}\right]+\beta \left[\begin{array}{c}0\\ 1\end{array}\right]=\left[\begin{array}{c}\alpha \\ \beta \end{array}\right]}$ or ${\displaystyle \alpha |1⟩+\beta |0⟩=\left[\begin{array}{c}\alpha \\ \beta \end{array}\right]}$ using Dirac notation. The state of the entire ${\displaystyle 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 ${\displaystyle S(n)}$ qubits is a single state vector which has ${\displaystyle 2^{S(n)}}$ dimensions and entries that are the amplitudes associated with each basis state or component vector. Therefore, ${\displaystyle 2^{S(n)}}$amplitudes must be accounted for with a ${\displaystyle 2^{S(n)}}$ dimensional complex vector which is the state vector for the ${\displaystyle S(n)}$ qubit system. 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 ${\displaystyle 2^{S(n)}}$ amplitudes. To do this ${\displaystyle O(T(n))}$ bits of precision are sufficient for encoding each amplitude. So it takes ${\displaystyle O(2^{S(n)}T(n))}$ classical bits to account for the state vector of the ${\displaystyle S(n)}$ qubit system. Next the application of the ${\displaystyle T(n)}$ quantum gates on ${\displaystyle 2^{S(n)}}$ amplitudes must be accounted for. The quantum gates can be represented as ${\displaystyle 2^{S(n)}\times 2^{S(n)}}$ sparse matrices. So to account for the application of each of the ${\displaystyle T(n)}$ quantum gates, the state vector must be multiplied by a ${\displaystyle 2^{S(n)}\times 2^{S(n)}}$ sparse matrix for each of the ${\displaystyle T(n)}$ quantum gates. Every time the state vector is multiplied by a ${\displaystyle 2^{S(n)}\times 2^{S(n)}}$ sparse matrix, ${\displaystyle O(2^{S(n)})}$ arithmetic operations must be performed. Therefore, there are ${\displaystyle O(2^{S(n)}T(n{)}^2)}$ bit operations for every quantum gate applied to the state vector. So ${\displaystyle O(2^{S(n)}T(n{)}^2)}$ classical gate are needed to simulate ${\displaystyle S(n)}$ qubit circuit with just one quantum gate. Therefore, ${\displaystyle O(2^{S(n)}T(n{)}^3)}$ classical gates are needed to simulate a quantum circuit of ${\displaystyle S(n)}$ qubits with ${\displaystyle T(n)}$ quantum gates. 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 ${\displaystyle \mathsf{B}\mathsf{P}\mathsf{P}\subseteq \mathsf{B}\mathsf{Q}\mathsf{P}}$.

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 ${\displaystyle G=(N,E)}$, where N is the set of vertices, or nodes, and E is the set of edges.

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: ${\displaystyle M\in \{0,1\}{a}^{n\mathrm{X}n}}$, with ${\displaystyle M_{ij}=1}$, if and only if ${\displaystyle (v_i,v_j)\in E}$.

Adjacency array model

Next, there is the slightly more complicated adjacency array model built on the idea of adjacency lists, where every vertex, ${\displaystyle u}$, is associated with an array of neighboring vertices such that ${\displaystyle f_i:[d_i^{+}]\to [n]}$, for the out-degrees of vertices ${\displaystyle d_i^{+},...,d_n^{+}}$, where ${\displaystyle n}$ is the minimum value of the upper bound of this model, and ${\displaystyle f_i(j)}$ returns the "${\displaystyle j^{th}}$" vertex adjacent to ${\displaystyle i}$. Additionally, the adjacency array model satisfies the simple graph condition, ${\displaystyle \mathrm{\forall }i\in [n],j,j^{\prime }\in [k],j\ne j^{\prime }:f_i(j)\ne f_i(j^{\prime })}$, 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).

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	${\displaystyle \mathrm{\Theta }(n^{3/2})}$	${\displaystyle \mathrm{\Theta }(\sqrt{nm})}$
Connectivity	${\displaystyle \mathrm{\Theta }(n^{3/2})}$	${\displaystyle \mathrm{\Theta }(n)}$
Strong connectivity	${\displaystyle \mathrm{\Theta }(n^{3/2})}$	${\displaystyle \mathrm{\Omega }(\sqrt{nm})}$, ${\displaystyle O(\sqrt{nm\log (n)})}$
Single source shortest path	${\displaystyle \mathrm{\Omega }(n^{3/2})}$, ${\displaystyle O(n^{3/2}{\log }^{2}n)}$	${\displaystyle \mathrm{\Omega }(\sqrt{nm})}$, ${\displaystyle O(\sqrt{nm}{\log }^2(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 ${\displaystyle \mathrm{\Theta }(n^{3/2})}$, but when the array model is used, the complexity is ${\displaystyle \mathrm{\Theta }(n)}$. Additionally, for brevity, we use the shorthand ${\displaystyle m}$ in certain cases, where ${\displaystyle m=\mathrm{\Theta }(n^2)}$. 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\left(\sqrt{N}\right)$, a quadratic improvement over the best possible classical query complexity ${\displaystyle O(N)}$, which is a linear search. Grover's algorithm is asymptotically optimal; in fact, it uses at most a ${\displaystyle 1+o(1)}$ fraction more queries than the best possible algorithm.

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 ${\displaystyle f:\{0,1{\}}^n\to \{0,1\}}$ is constant or balanced, those being the only two possibilities. The only way to evaluate the function ${\displaystyle 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 ${\displaystyle 2^n}$ possible inputs, the query complexity of the most efficient classical deterministic algorithm is ${\displaystyle 2^{n-1}+1}$. 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 ${\displaystyle 1}$.

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 hidden variable quantum computer based on Bohmian Mechanics could implement a search of an N-item database in at most ${\displaystyle O(\sqrt[3]{N})}$ steps, a slight speedup over Grover's algorithm, which runs in ${\displaystyle O(\sqrt{N})}$ steps. Note, however, that neither search method would allow quantum computers to solve NP-complete problems in polynomial time. 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.