東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

On the complexity of classical and q...

Bessen, Arvid J.

Linked to FindBook

Google Book

Amazon

博客來

On the complexity of classical and quantum algorithms for numerical problems in quantum mechanics.

Record Type:	Language materials, printed : Monograph/item
Title/Author:	On the complexity of classical and quantum algorithms for numerical problems in quantum mechanics./
Author:	Bessen, Arvid J.
Description:	146 p.
Notes:	Adviser: Joseph F. Traub.
Contained By:	Dissertation Abstracts International69-01B.
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3299247
ISBN:	9780549431008

On the complexity of classical and quantum algorithms for numerical problems in quantum mechanics.
Bessen, Arvid J.

On the complexity of classical and quantum algorithms for numerical problems in quantum mechanics. - 146 p.

Adviser: Joseph F. Traub.

Thesis (Ph.D.)--Columbia University, 2008.

Our understanding of complex quantum mechanical processes is limited by our inability to solve the equations that govern them except for simple cases. Numerical simulation of quantum systems appears to be our best option to understand, design and improve quantum systems. It turns out, however, that computational problems in quantum mechanics are notoriously difficult to treat numerically. The computational time that is required often scales exponentially with the size of the problem.

ISBN: 9780549431008Subjects--Topical Terms:

626642
Computer Science.

On the complexity of classical and quantum algorithms for numerical problems in quantum mechanics.
LDR:05879nam 2200337 a 45 001 963017
005 20110830
008 110831s2008 ||||||||||||||||| ||eng d
020 $a 9780549431008
035 $a (UMI)AAI3299247
035 $a AAI3299247
040 $a UMI $c UMI
100 1 $a Bessen, Arvid J. $3 1286076
245 1 0 $a On the complexity of classical and quantum algorithms for numerical problems in quantum mechanics.
300 $a 146 p.
500 $a Adviser: Joseph F. Traub.
500 $a Source: Dissertation Abstracts International, Volume: 69-01, Section: B, page: 0404.
502 $a Thesis (Ph.D.)--Columbia University, 2008.
520 $a Our understanding of complex quantum mechanical processes is limited by our inability to solve the equations that govern them except for simple cases. Numerical simulation of quantum systems appears to be our best option to understand, design and improve quantum systems. It turns out, however, that computational problems in quantum mechanics are notoriously difficult to treat numerically. The computational time that is required often scales exponentially with the size of the problem.
520 $a One of the most radical approaches for treating quantum problems was proposed by Feytiman in 1982 [46]: he suggested that quantum mechanics itself showed a promising way to simulate quantum physics. This idea, the so called quantum computer, showed its potential convincingly in one important regime with the development of Shor's integer factorization algorithm which improves exponentially on the best known classical algorithm.
520 $a In this thesis we explore six different computational problems from quantum mechanics, study their computational complexity and try to find ways to remedy them. In the first problem we investigate the reasons behind the improved performance of Shor's and similar algorithms. We show that the key quantum part in Shor's algorithm, the quantum phase estimation algorithm, achieves its good performance through the use of power queries and we give lower bounds for all phase estimation algorithms that use power queries that match the known upper bounds. Our research indicates that problems that allow the use of power queries will achieve similar exponential improvements over classical algorithms. We then apply our lower bound technique for power queries to the Sturm-Liouville eigenvalue problem and show matching lower bounds to the upper bounds of Papageorgiou and Wozniakowski [85]. It seems to be very difficult, though, to find nontrivial instances of the Sturm-Lionville problem for which power queries can be simulated efficiently.
520 $a A quantum computer differs from a classical computer that uses randomness, because it allows "negative probabilities" that can cancel each other (destructive interference). Ideally we would like to transfer classical randomized algorithms to the quantum computer and get speed improvements. One of the simplest classical randomized algorithm is the random walk and we study the behavior of the continuous-time quantum random walk. We analyze this random walk in one dimension and give analytical formulas for its behavior that demonstrate its interference properties. Is interference or cancellation really the most important advantage that a quantum computer has over a classical computer? To answer that question we study the class StociMA of "stochastic quantum" algorithms that only use classical gates, but are given a quantum "witness", i.e. an arbitrary quantum state that can guide the algorithm in computing the correct answer, but should not be able to "fool" it. We show that there exists a complete problem for this class, which we call the stoquastic local Hamiltonian problem. In this problem we try to compute the lowest eigenvalue of a Hamiltonian with interactions that span only a fixed number of particles and all contribute negatively. With the help of this problem we prove that MA &sube; StocIMA &sube; SBP ∪ QMA. This shows that interference is one of the most important parts of quantum computation.
520 $a The simulation of the evolution of a general quantum system in time requires a computational time that is exponential in the dimension of the system. But maybe the problem that we ask for is too general and we can simulate special systems in polynomial time. In particular it would be interesting to study quantum systems of "limited energy", i.e. for which the state at starting time consists mainly out of components with small energy. We model this in the theory of weighted reproducing kernel Hilbert spaces with two different sets of weights: product weights and finite-order weights. We will show that the information cost of computing the evolution for starting states from these spaces is tractable, i.e. the cost does not grow exponentially with the dimension of the problem.
520 $a Finally we study a computational problem from lattice quantum chromodynamics (QCD). In most popular algorithms that treat problems in QCD the (gauged) Dirac matrix has to be inverted numerous times. Since this matrix is large, sparse, and ill-conditioned, iterative approaches have to be used. Unfortunately a direct application of methods like conjugate gradient (CC) or minimal residual algorithms seem to give poor performance in practice. We study a newly proposed multigrid method, adaptive smoothed aggregation [29], that has promise to overcome these difficulties We show that while classical CG's convergence becomes worse as the matrix becomes almost singular, adaptive smoothed aggregation will still perform well.
590 $a School code: 0054.
650 4 $a Computer Science. $3 626642
650 4 $a Physics, Theory. $3 1019422
690 $a 0753
690 $a 0984
710 2 $a Columbia University. $3 571054
773 0 $t Dissertation Abstracts International $g 69-01B.
790 $a 0054
790 1 0 $a Traub, Joseph F., $e advisor
791 $a Ph.D.
792 $a 2008
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3299247