자료유형  

 학위논문

Control Number  

0016931145

International Standard Book Number  

9798380623308

Dewey Decimal Classification Number  

004

Main Entry-Personal Name  

Nirkhe, Chinmay.

Publication, Distribution, etc. (Imprint  

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

Publication, Distribution, etc. (Imprint  

Ann Arbor : ProQuest Dissertations & Theses, 2022

Physical Description  

1 online resource(76 p.)

General Note  

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

General Note  

Advisor: Vazirani, Umesh.

Dissertation Note  

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

Restrictions on Access Note  

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

Summary, Etc.  

요약The quantum PCP conjecture is one of the central open questions in quantum complexity theory. It asserts that calculating even a rough approximation to the ground energy of a local Hamiltonian is intractable even for quantum devices. The widely believed separation between the complexity classes NP and QMA necessitates that polynomial length classical proofs do not exist for calculating the ground energy. This further implies that low-energy states of local Hamiltonians cannot be described by constant depth quantum circuits. The No low-energy trivial states (NLTS) conjecture by Freedman and Hastings posited the existence of such Hamiltonians.This thesis describes a line of research culminating in a proof of the NLTS conjecture, first presented by Anshu, Breuckmann, and Nirkhe. The construction is based on quantum error correction and the thesis elaborates on how error correction, local Hamiltonians, and low-depth quantum circuits are related.

Subject Added Entry-Topical Term  

Computer science.

Subject Added Entry-Topical Term  

Quantum physics.

Subject Added Entry-Topical Term  

Mechanics.

Index Term-Uncontrolled  

Complexity theory

Index Term-Uncontrolled  

Error correction

Index Term-Uncontrolled  

Lower bounds

Index Term-Uncontrolled  

Probabilistically checkable proofs

Index Term-Uncontrolled  

Hamiltonians

Added Entry-Corporate Name  

University of California, Berkeley Computer Science

Host Item Entry  

Dissertations Abstracts International. 85-05B.

Host Item Entry  

Dissertation Abstract International

Electronic Location and Access  

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

Control Number  

joongbu:641725