  Quantum computers are expected to revolutionize our ability to process
information. The advancement from classical to quantum computing is a product
of our advancement from classical to quantum physics -- the more our
understanding of the universe grows, so does our ability to use it for
computation. A natural question that arises is, what will physics allow in the
future? Can more advanced theories of physics increase our computational power,
beyond quantum computing?
  An active field of research in physics studies theoretical phenomena outside
the scope of explainable quantum mechanics, that form when attempting to
combine Quantum Mechanics (QM) with General Relativity (GR) into a unified
theory of Quantum Gravity (QG). QG is known to present the possibility of a
quantum superposition of causal structure and event orderings. In the
literature of quantum information theory, this translates to a superposition of
unitary evolution orders.
  In this work we show a first example of a natural computational model based
on QG, that provides an exponential speedup over standard quantum computation
(under standard hardness assumptions). We define a model and complexity measure
for a quantum computer that has the ability to generate a superposition of
unitary evolution orders, and show that such computer is able to solve in
polynomial time two of the fundamental problems in computer science: The Graph
Isomorphism Problem ($\mathsf{GI}$) and the Gap Closest Vector Problem
($\mathsf{GapCVP}$), with gap $O\left( n \sqrt{n} \right)$. These problems are
believed by experts to be hard to solve for a regular quantum computer.
Interestingly, our model does not seem overpowered, and we found no obvious way
to solve entire complexity classes that are considered hard in computer
science, like the classes $\mathbf{NP}$ and $\mathbf{SZK}$.
