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

YouTube

On the Power of Nonstandard Quantum Oracles - Complexity Theory and Oracle Models

Squid: Schools for Quantum Information Development via YouTube

Overview

Watch a conference talk from TQC 2023 exploring how different oracle designs impact the complexity of quantum property testing problems. Delve into research examining regular graphs of even degree encoded as invertible functions and presented through various oracle models. Learn about a one-query QMA protocol for testing disconnected subsets in graphs, and discover through representation theory why classical witnesses cannot help quantum verifiers efficiently decide this problem with in-place oracles. Explore an intriguing finding where simple oracle modifications prevent quantum verifiers from efficient decision-making even with unlimited witness access. Follow along as the presentation covers key concepts including complexity theory, quantum oracles, QCMA, spectral testing, randomized oracles, proof techniques, phase oracles, and pseudorandom states. Originally presented at the 18th Conference on the Theory of Quantum Computation, Communication and Cryptography at the University of Aveiro, this 23-minute talk provides theoretical insights into quantum information science and computational complexity.

Syllabus

Introduction
Complexity Theory
Oracles
Quantum Oracles
QCMA
Using a Quantum Oracle
Power of an Oracle
Complexity
Results
Problem
Quantum algorithm
Spectral test
Randomized oracles
Proof technique
Other Oracle models
Phase Oracle
Why is this problem so hard
Phase transition
Pseudorandom states

Taught by

Squid: Schools for Quantum Information Development

Reviews

Start your review of On the Power of Nonstandard Quantum Oracles - Complexity Theory and Oracle Models

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.