서브메뉴
검색
Quantum Complexity of Physically Inspired Problems and Computational Resources
Quantum Complexity of Physically Inspired Problems and Computational Resources
상세정보
- 자료유형
- 학위논문 서양
- 최종처리일시
- 20260311091518.5
- ISBN
- 9798270229580
- DDC
- 530.12
- 저자명
- Yirka, Justin
- 서명/저자
- Quantum Complexity of Physically Inspired Problems and Computational Resources / Justin Yirka
- 발행사항
- [Sl] : The University of Texas at Austin, 2025
- 형태사항
- 1 electronic resource (177 pages)
- 주기사항
- Source: Dissertations Abstracts International, Volume: 87-06, Section: B.
- 주기사항
- Advisors: Aaronson, Scott Committee members: Fefferman, Bill; Soloveichik, David; Hunter-Jones, Nick.
- 학위논문주기
- - Ph.D. : The University of Texas at Austin, 2025.
- 초록/해제
- 요약This dissertation presents results on the computational complexity of problems and resources inspired by quantum physics. These contributions sharpen the computational challenges posed by quantum systems and clarify the physical limits of computation in a quantum world. The first part studies the complexity of estimating properties of physical systems described by local interactions. These Hamiltonian problems are quantum analogs of constraint satisfaction problems disguised in the language of physics. I prove it remains difficult to estimate 1-qudit measurements on the low-energy space of even a 1-dimensional line of particles. Then, I discuss the complexity of estimating spectral gaps. I also fully classify the complexity of estimating optimal product states for Hamiltonian families generated by sets of allowed two-body interactions. The second part explores the power of quantum computational resources. I establish limitations on the usefulness of quantum states by showing that multiple rounds of entangled proofs are useless in certain non-interactive quantum proof systems. I also give a corrected proof of an upper bound on the power of polynomial-size circuits even when using trusted quantum advice states. Finally, I study quantum queries to an unconventional but classical model, in-place oracles, and introduce a new algorithm for permutation inversion, equivalent to unstructured search.
- 언어주기
- English
- 일반주제명
- Quantum physics
- 일반주제명
- Computational physics
- 일반주제명
- Particle physics
- 키워드
- Quantum systems
- 키워드
- Computation
- 키워드
- Entangled proofs
- 기타저자
- The University of Texas at Austin Computer Science
- 기본자료저록
- Dissertations Abstracts International. 87-06B.
- 전자적 위치 및 접속
- 로그인 후 원문을 볼 수 있습니다.
MARC
008260311s2025 us eng d■001000017361152
■00520260311091518.5
■006m o d
■007cr|nu||||||||
■020 ▼a9798270229580
■040 ▼aMiAaPQD▼beng▼cMiAaPQD▼erda
■082 ▼a530.12
■1001 ▼aYirka, Justin▼eauthor.
■24510▼aQuantum Complexity of Physically Inspired Problems and Computational Resources ▼cJustin Yirka
■260 ▼a[Sl]▼bThe University of Texas at Austin▼c2025
■264 1▼aAnn Arbor▼bProQuest Dissertations & Theses▼c2025
■300 ▼a1 electronic resource (177 pages)
■336 ▼atext▼btxt▼2rdacontent
■337 ▼acomputer▼bc▼2rdamedia
■338 ▼aonline resource▼bcr▼2rdacarrier
■500 ▼aSource: Dissertations Abstracts International, Volume: 87-06, Section: B.
■500 ▼aAdvisors: Aaronson, Scott Committee members: Fefferman, Bill; Soloveichik, David; Hunter-Jones, Nick.
■5021 ▼bPh.D.▼cThe University of Texas at Austin▼d2025.
■520 ▼aThis dissertation presents results on the computational complexity of problems and resources inspired by quantum physics. These contributions sharpen the computational challenges posed by quantum systems and clarify the physical limits of computation in a quantum world. The first part studies the complexity of estimating properties of physical systems described by local interactions. These Hamiltonian problems are quantum analogs of constraint satisfaction problems disguised in the language of physics. I prove it remains difficult to estimate 1-qudit measurements on the low-energy space of even a 1-dimensional line of particles. Then, I discuss the complexity of estimating spectral gaps. I also fully classify the complexity of estimating optimal product states for Hamiltonian families generated by sets of allowed two-body interactions. The second part explores the power of quantum computational resources. I establish limitations on the usefulness of quantum states by showing that multiple rounds of entangled proofs are useless in certain non-interactive quantum proof systems. I also give a corrected proof of an upper bound on the power of polynomial-size circuits even when using trusted quantum advice states. Finally, I study quantum queries to an unconventional but classical model, in-place oracles, and introduce a new algorithm for permutation inversion, equivalent to unstructured search.
■546 ▼aEnglish
■590 ▼aSchool code: 0227
■650 4▼aQuantum physics
■650 4▼aComputational physics
■650 4▼aParticle physics
■653 ▼aQuantum systems
■653 ▼aComputation
■653 ▼aEntangled proofs
■653 ▼aQuantum advice states
■7102 ▼aThe University of Texas at Austin▼bComputer Science.▼edegree granting institution.
■7201 ▼aAaronson, Scott▼edegree supervisor.
■7730 ▼tDissertations Abstracts International▼g87-06B.
■85640▼uhttp://www.riss.kr/pdu/ddodLink.do?id=T17361152▼nKERIS▼z이 자료의 원문은 한국교육학술정보원에서 제공합니다.
