Quantum algorithm and circuit design solving the Poisson equation
This is a modal window.
Das Video konnte nicht geladen werden, da entweder ein Server- oder Netzwerkfehler auftrat oder das Format nicht unterstützt wird.
Formale Metadaten
| Titel |
| |
| Serientitel | ||
| Anzahl der Teile | 63 | |
| Autor | ||
| Lizenz | CC-Namensnennung 3.0 Unported: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. | |
| Identifikatoren | 10.5446/39039 (DOI) | |
| Herausgeber | ||
| Erscheinungsjahr | ||
| Sprache |
Inhaltliche Metadaten
| Fachgebiet | ||
| Genre | ||
| Abstract |
|
00:00
MotorElektrostatische AufladungSpeckle-InterferometrieComputeranimation
00:06
Kette <Zugmittel>Computeranimation
00:13
Domäne <Kristallographie>ProfilwalzenWarmumformenComputeranimation
00:24
Domäne <Kristallographie>Computeranimation
00:28
Domäne <Kristallographie>Computeranimation
00:31
FehlprägungZeitdiskretes SignalToleranzanalyseDrachenpunktSchubvektorsteuerungMatrize <Umformen>Domäne <Kristallographie>FehlprägungGasturbineComputeranimation
01:11
FehlprägungMatrize <Umformen>Computeranimation
01:21
FehlprägungBrennpunkt <Optik>FehlprägungComputeranimation
01:36
FehlprägungEisenbahnbetriebBrennpunkt <Optik>Matrize <Umformen>EisenbahnbetriebComputeranimation
02:03
Matrize <Umformen>NetztransformatorFACTS-AnlageComputeranimation
02:09
Matrize <Umformen>FACTS-AnlageComputeranimation
02:14
FehlprägungSchlichte <Textiltechnik>Matrize <Umformen>SchaltplanComputeranimation
02:33
ReihenschwingkreisFehlprägungMatrize <Umformen>Reziprokes GitterQuantenschaltungMatrize <Umformen>Blatt <Papier>ModulationFehlprägungSchlichte <Textiltechnik>AtmosphäreComputeranimation
03:02
Computeranimation
03:05
BogenentladungComputeranimation
Transkript: Englisch(automatisch erzeugt)
00:01
Poisson equation is important in many areas of science and engineering such as electrostatic calculation, computational fluid dynamics, image processing, theory of Markov chains, just to name a few. This is its general mathematical form. Here the function fx is given and we seek the solution ux.
00:22
In this work, we consider x defined on a d-dimensional cubic domain with Dirichlet boundary condition. For example, in 2-dimension, the domain is a square. In order to solve the equation numerically, the most common method is to discretize the domain with a grid. At each node, the second derivative can be approximated in terms of the values on the neighboring nodes.
00:43
Applying the same finite difference discretization on each node of the grid, the Poisson equation with Dirichlet boundary condition can be recast as a linear system where A is a symmetric positive definite matrix. Thus, vectors u and f contain the values of the functions ux, fx on the discrete nodes of the grid.
01:02
Classically, to solve a d-dimensional problem with error-tolerance epsilon, the time and memory needed for all classical algorithms to find the solution scales at least exponentially as a function of dimension d because the matrix A grows exponentially as d increases for the same epsilon. This is commonly termed as the curse of dimensionality. Our quantum algorithm, however, is able
01:24
to find the solution with a cost that is polynomial in the logarithm of inverse error and almost linear in dimension d, achieving an exponential speedup over the classical algorithms. Now let's focus on the quantum algorithm. Apart from ancilla qubits, the input to the algorithm is a superposition of function evaluations of the right-hand side of the Poisson equation.
01:46
The output of the algorithm is a quantum state encoding the solution. The quantum circuit is efficient in terms of both quantum operations and number of qubits needed. The final state solution can be used for computing the expectation value of a certain quantum mechanical operator M.
02:02
An important subroutine of the algorithm is the Hamiltonian simulation of the Poisson matrix. To efficiently implement the simulation, we take advantage of the fact that the Poisson matrix can be diagonalized using sine transform. The exponential of the diagonal matrix is efficiently implemented using an eigenvalue simulation algorithm,
02:21
and the sine transform is implemented using a quantum circuit based on quantum Fourier transform. The overall cost of the Hamiltonian simulation is polynomial in the logarithm of the matrix size and inverse error. In summary, the main results of the paper include an efficient quantum algorithm and scalable quantum circuit design which finds the approximate solution to the Poisson equation with error epsilon.
02:44
It is an open problem to determine if or when a Hamiltonian can be simulated with cost scaling that is polyn logarithmic in both the matrix size and inverse error. We show that this is possible for Poisson matrix. Furthermore, in this paper we provide efficient quantum circuit modules which can be useful in other problems.
Empfehlungen
Serie mit 25 Medien