JUNE 28, 2019 by Lisa Zyga , Phys.org
Information and gravity may seem like completely different things, but one thing they have in common is that they can both be described in the framework of geometry. Building on this connection, a new paper suggests that the rules for optimal quantum computation are set by gravity.
Physicists Paweł Caputa at Kyoto University and Javier Magan at the Instituto Balseiro, Centro Atómico de Bariloche in Argentina have published their paper on the link between quantum computing and gravity in a recent issue of Physical Review Letters.
In the field of computational complexity, one of the main ideas is minimizing the cost (in terms of computational resources) to solve a problem. In 2006, Michael Nielsen demonstrated that, when viewed in the context of differential geometry, computational costs can be estimated by distances. This means that minimizing computational costs is equivalent to finding minimal “geodesics,” which are the shortest possible distances between two points on a curved surface.
As this geometric perspective is very similar to the concepts used to describe gravity, Nielsen’s results have led researchers to investigate possible connections between computational complexity and gravity. But the work is challenging, and researchers are still trying to figure out basic questions such as how to define “complexity” in holographic models related to quantum gravity, in particular, conformal field theory. Currently there are many different proposals for laying the foundations in this area.
The main purpose of the new paper is to bring these different ideas together by proposing a universal description of complexity that depends only on a single quantity (central charge). This leads to the discovery of connections between complexity and concepts in (quantum) gravity which, in turn, leads to interesting implications such as the possibility that gravity governs the rules for optimal quantum computation.
“Recently, quantum computation theorists (including Nielsen) put forward the idea that the complexity of quantum circuits can be estimated by the length of the shortest geodesic in the ‘complexity geometry of unitary transformations,'” Caputa told Phys.org. “We showed that, in two-dimensional conformal field theories with quantum gates given by the energy-momentum tensor, the ‘length’ of such geodesics is computed by (the action of) two-dimensional gravity.
“Finding the minimal length on the complexity geometry, in our setup, is equivalent to solving the equations of gravity. This is what we meant by gravity setting rules for optimal computations in 2-D conformal field theories.”
This perspective suggests that gravity could be useful in estimating computational complexity and identifying the most efficient computational methods for solving problems.
“The notion of complexity of a certain task tells us how difficult it is to perform it using our available tools,” Magan said. “In the quantum theory of computation, this notion is generalized to the complexity of quantum circuits built out from quantum gates. Estimating it is in general a difficult problem.
“We showed that there are families of quantum systems where the complexity of certain universal tasks is well estimated using classical gravity (general relativity). Over the years, using holography and Anti-de Sitter/conformal field theories, we have been learning that gravity is intimately related to quantum information. The lesson from our findings is that gravity may also teach us how to perform quantum computation in physical systems in the most efficient way.”