Quantum Algorithms in a Superposition of Spacetimes

• URL: http://arxiv.org/abs/2403.02937v3
• Date: Sun, 12 May 2024 12:20:27 GMT
• Title: Quantum Algorithms in a Superposition of Spacetimes
• Authors: Omri Shmueli,
• Abstract summary: Quantum computers are expected to revolutionize our ability to process information. We show a first example of a natural computational model based on Quantum Gravity (QG) We show that a quantum computer is able to solve in time two of the fundamental problems in computer science.
• Score: 5.475280561991127
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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}$.

Related papers

• The QUATRO Application Suite: Quantum Computing for Models of Human Cognition [49.038807589598285]
  We unlock a new class of applications ripe for quantum computing research -- computational cognitive modeling. We release QUATRO, a collection of quantum computing applications from cognitive models.
  arXiv  Detail & Related papers  (2023-09-01T17:34:53Z)
• Quantum Computing and the Riemann Hypothesis [0.0]
  Quantum computing is a promising new area of computing with quantum algorithms offering a potential speedup over classical algorithms. We show how to obtain functions as states in supersymmetric quantum mechanics.
  arXiv  Detail & Related papers  (2023-03-07T04:28:54Z)
• Quantum Machine Learning: from physics to software engineering [58.720142291102135]
  We show how classical machine learning approach can help improve the facilities of quantum computers. We discuss how quantum algorithms and quantum computers may be useful for solving classical machine learning tasks.
  arXiv  Detail & Related papers  (2023-01-04T23:37:45Z)
• Recent Advances for Quantum Neural Networks in Generative Learning [98.88205308106778]
  Quantum generative learning models (QGLMs) may surpass their classical counterparts. We review the current progress of QGLMs from the perspective of machine learning. We discuss the potential applications of QGLMs in both conventional machine learning tasks and quantum physics.
  arXiv  Detail & Related papers  (2022-06-07T07:32:57Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions. For its practicability and wide-applicability, we give a brief review of typical graph learning techniques. We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
  arXiv  Detail & Related papers  (2022-02-19T02:56:47Z)
• Quantum Computing for Inflationary, Dark Energy and Dark Matter Cosmology [1.1706540832106251]
  Quantum computing is an emerging new method of computing which excels in simulating quantum systems. We show how to apply the Variational Quantum Eigensolver (VQE) and Evolution of Hamiltonian (EOH) algorithms to solve the Wheeler-DeWitt equation. We find excellent agreement with classical computing results and describe the accuracy of the different quantum algorithms.
  arXiv  Detail & Related papers  (2021-05-28T14:04:11Z)
• On quantum neural networks [91.3755431537592]
  We argue that the concept of a quantum neural network should be defined in terms of its most general function. Our reasoning is based on the use of the Feynman path integral formulation in quantum mechanics.
  arXiv  Detail & Related papers  (2021-04-12T18:30:30Z)
• Towards Cosmological Simulations of Dark Matter on Quantum Computers [0.0]
  Quantum computers can perform some calculations exponentially faster than classical computers. Quantum circuits act linearly on quantum states, so nonlinearities (e.g. self-gravity in cosmological simulations) pose a significant challenge. Here we outline one potential approach to overcome this challenge and solve the (nonlinear) Schrodinger-Poisson equations for the evolution of self-gravitating dark matter.
  arXiv  Detail & Related papers  (2021-01-14T19:00:06Z)
• Quantum walk processes in quantum devices [55.41644538483948]
  We study how to represent quantum walk on a graph as a quantum circuit. Our approach paves way for the efficient implementation of quantum walks algorithms on quantum computers.
  arXiv  Detail & Related papers  (2020-12-28T18:04:16Z)
• Efficient Simulation of Loop Quantum Gravity -- A Scalable Linear-Optical Approach [0.0]
  A leading approach is Loop Quantum Gravity (LQG) We design a linear-optical simulator such that the evolution of the optical quantum gates simulates the spinfoam amplitudes of LQG. This work opens a new way to relate quantum gravity to quantum information and will expand our understanding of the theory.
  arXiv  Detail & Related papers  (2020-03-06T20:04:20Z)
• Quantum algorithms for quantum chemistry and quantum materials science [2.867517731896504]
  We briefly describe central problems in chemistry and materials science, in areas of electronic structure, quantum statistical mechanics, and quantum dynamics, that are of potential interest for solution on a quantum computer. We take a detailed snapshot of current progress in quantum algorithms for ground-state, dynamics, and thermal state simulation, and analyze their strengths and weaknesses for future developments.
  arXiv  Detail & Related papers  (2020-01-10T22:49:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.