BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//UW QuantumX - ECPv6.16.2//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://www.quantumx.washington.edu
X-WR-CALDESC:Events for UW QuantumX
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:America/Los_Angeles
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20240310T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20241103T090000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20250309T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20251102T090000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:-0800
TZOFFSETTO:-0700
TZNAME:PDT
DTSTART:20260308T100000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0700
TZOFFSETTO:-0800
TZNAME:PST
DTSTART:20261101T090000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/Los_Angeles:20251202T133000
DTEND;TZID=America/Los_Angeles:20251202T150000
DTSTAMP:20260525T071458
CREATED:20251202T182819Z
LAST-MODIFIED:20251209T195015Z
UID:7661-1764682200-1764687600@www.quantumx.washington.edu
SUMMARY:Separating QMA and QCMA with a classical oracle\, Chinmay Nirkhe
DESCRIPTION:Abstract:  \n\n\n\nWe construct a classical oracle proving that\, in a relativized setting\, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation — the oracle describes two subsets of the boolean hypercube\, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a “Forrelation” matrix between two sets that are accessible through membership queries. \n\n\n\nOur lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution\, while a quantum witness is a “use once” object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result\, which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA\, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons — a novel “second quantization” perspective on compressed oracle techniques\, which may be of independent interest. Using this compressed perspective on the sampling problem\, we prove the sampling hardness result\, completing the proof. \n\n\n\nJoint work with John Bostanci\, Jonas Haferkamp\, and Mark Zhandry: https://arxiv.org/abs/2511.09551 
URL:https://www.quantumx.washington.edu/calendar/separating-qma-and-qcma-with-a-classical-oracle/
LOCATION:Washington
CATEGORIES:Computer Science & Engineering
END:VEVENT
END:VCALENDAR