Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis

Squid: Schools for Quantum Information Development via YouTube

Overview

Learn about parameterized complexity in quantum computing through a conference talk presented at the 18th Theory of Quantum Computation Conference (TQC 2023). Explore the weighted local Hamiltonian problem, where quantum states are constrained by specific Hamming weights, and understand its implications for quantum complexity theory. Delve into the proof that this problem belongs to QW[1] while being hard for QM[1], and examine how these findings relate to fixed-parameter quantum tractability and the quantum exponential time hypothesis. Follow along as the speaker covers classical complexity theory, quantum parameterized complexity, quantum circuits, sparse Hamiltonians, and presents detailed proof sketches with lower bounds. Gain insights into how Hamming weight constraints can represent physical limitations like excitation numbers or particle counts in quantum systems.

Syllabus

Introduction
Parameterized Complexity
Why
Classical Complexity Theory
Fixed Parameterized Complexity
Exponential Time Hypothesis
Quantum Parameterized Complexity
Defining a Quantum Circuit
Quantum Weight
Quantum Circuit
Results
Proof Sketch
Sparse Hamiltonian
Lower Bounds
Proof
Conclusion

Taught by

Squid: Schools for Quantum Information Development

Reviews

Start your review of Parameterized Complexity of Weighted Local Hamiltonian Problems and the Quantum Exponential Time Hypothesis

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.