서브메뉴
검색
Lower Bounds on the Complexity of Quantum Proofs- [electronic resource]
Lower Bounds on the Complexity of Quantum Proofs- [electronic resource]
상세정보
- 자료유형
- 학위논문
- 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
MARC
008240221s2022 ulk 00 kor■001000016931145
■00520240214095926
■006m o d
■007cr#unu||||||||
■020 ▼a9798380623308
■035 ▼a(MiAaPQ)AAI29327432
■040 ▼aMiAaPQ▼cMiAaPQ
■0820 ▼a004
■1001 ▼aNirkhe, Chinmay.
■24510▼aLower Bounds on the Complexity of Quantum Proofs▼h[electronic resource]
■260 ▼a[S.l.]▼bUniversity of California, Berkeley. ▼c2022
■260 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2022
■300 ▼a1 online resource(76 p.)
■500 ▼aSource: Dissertations Abstracts International, Volume: 85-05, Section: B.
■500 ▼aAdvisor: Vazirani, Umesh.
■5021 ▼aThesis (Ph.D.)--University of California, Berkeley, 2022.
■506 ▼aThis item must not be sold to any third party vendors.
■520 ▼aThe 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.
■590 ▼aSchool code: 0028.
■650 4▼aComputer science.
■650 4▼aQuantum physics.
■650 4▼aMechanics.
■653 ▼aComplexity theory
■653 ▼aError correction
■653 ▼aLower bounds
■653 ▼aProbabilistically checkable proofs
■653 ▼aHamiltonians
■690 ▼a0984
■690 ▼a0599
■690 ▼a0346
■71020▼aUniversity of California, Berkeley▼bComputer Science.
■7730 ▼tDissertations Abstracts International▼g85-05B.
■773 ▼tDissertation Abstract International
■790 ▼a0028
■791 ▼aPh.D.
■792 ▼a2022
■793 ▼aEnglish
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T16931145▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
■980 ▼a202402▼f2024
