자료유형  

 학위논문

Control Number  

0016931005

International Standard Book Number  

9798380618755

Dewey Decimal Classification Number  

004

Main Entry-Personal Name  

O'Gorman, Bryan.

Publication, Distribution, etc. (Imprint  

[S.l.] : University of California, Berkeley., 2021

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2021

Physical Description  

1 online resource(153 p.)

General Note  

Source: Dissertations Abstracts International, Volume: 85-04, Section: B.

General Note  

Advisor: Vazirani, Umesh;Whaley, K. Birgitta.

Dissertation Note  

Thesis (Ph.D.)--University of California, Berkeley, 2021.

Restrictions on Access Note  

This item must not be sold to any third party vendors.

Summary, Etc.  

요약Quantum computers now exist, and will likely continue to get bigger and better. But will they ever be useful? That is, are there real-world problems that future quantum computers will be able to solve well enough in a reasonable amount of time, but for which classical computers cannot do the same? This thesis presents a collection of results that together address this question from different directions. The first part limits the utility of quantum computers. We show how to characterize and minimize the cost (in time and memory) of simulating quantum computations on a classical computer in terms of the congestion (a graph property) of a graphical representation of the quantum computation. Therefore, for a quantum computation to have an advantage over classical computation, it must have large congestion. Even when that is the case, better classical simulations, costly though they may be, can help validate and develop quantum computers. We also prove that the fundamental problem of quantum chemistry, the electronic structure problem, is QMA-complete. Therefore, under standard complexity-theoretic assumptions, the solution must be represented using a quantum state, and yet still even quantum computers cannot efficiently find it. The second part includes methods for applying and compiling quantum algorithms in order to maximize the utility of the hardware we have, now and in the future. We introduce the strategy of generalized swap networks and show how to use them to compile quantum algorithms for quantum chemistry and classical optimization. We combine quantum computation with constraint programming in two ways: we show how to combine existing quantum algorithms to speed up the solution of constraint programming problems, which capture a wide range of realistic application domains, and also discuss the application of constraint programming to compiling quantum algorithms. We also present a framework for generalizing the Quantum Approximate Optimization Algorithm to what we call the Quantum Alternating Operator Ansatz. Many of the algorithms are heuristic, but by improving the efficiency of their implementation on actual devices, we improve our chances of successfully trying them out and seeing if they work or not.

Subject Added Entry-Topical Term  

Computer science.

Subject Added Entry-Topical Term  

Quantum physics.

Subject Added Entry-Topical Term  

Particle physics.

Index Term-Uncontrolled  

Quantum computers

Index Term-Uncontrolled  

Lower bounds

Index Term-Uncontrolled  

Upper bounds

Index Term-Uncontrolled  

Quantum simulation

Added Entry-Corporate Name  

University of California, Berkeley Electrical Engineering & Computer Sciences

Host Item Entry  

Dissertations Abstracts International. 85-04B.

Host Item Entry  

Dissertation Abstract International

Electronic Location and Access  

로그인을 한후 보실 수 있는 자료입니다.

Control Number  

joongbu:640873