Главная
Study mode:
on
1
Introduction
2
Parameterized Complexity
3
Why
4
Classical Complexity Theory
5
Fixed Parameterized Complexity
6
Exponential Time Hypothesis
7
Quantum Parameterized Complexity
8
Defining a Quantum Circuit
9
Quantum Weight
10
Quantum Circuit
11
Results
12
Proof Sketch
13
Sparse Hamiltonian
14
Lower Bounds
15
Proof
16
Conclusion
Description:
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.

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

Squid: Schools for Quantum Information Development
Add to list