A one-query lower bound for unitary synthesis and breaking quantum cryptography

Speaker: Fermi Ma , Berkeley

Date: Tuesday, November 21, 2023

Time: 4:00 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: KIVA G449

Event Type:

Room Description: KIVA G449

Host: Vinod Vaikuntanathan, Anand Natarajan, CSAIL MIT


Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to: seminars@csail.mit.edu, theory-seminars@csail.mit.edu

Reminder Subject: TALK: A one-query lower bound for unitary synthesis and breaking quantum cryptography

Abstract: The Unitary Synthesis Problem (Aaronson-Kuperberg 2007) asks whether any n-qubit unitary U can be implemented by an efficient quantum algorithm A augmented with an oracle that computes an arbitrary Boolean function f. In other words, can the task of implementing any unitary be efficiently reduced to the task of implementing any Boolean function?

In this work, we prove a one-query lower bound for unitary synthesis. We show that there exist unitaries U such that no quantum polynomial-time oracle algorithm A^f can implement U, even approximately, if it only makes one (quantum) query to f. Our approach also has implications for quantum cryptography: we prove (relative to a random oracle O) the existence of quantum cryptographic primitives that remain secure against all one-query adversaries A^f. Since such one-query algorithms can decide any language, solve any classical search problem, and even prepare any quantum state, this result suggests that implementing random unitaries and breaking quantum cryptography may be harder than all of these tasks.

No background in quantum computing will be assumed.

This is a joint work with Alex Lombardi and John Wright. arXiv: https://arxiv.org/pdf/2310.08870.pdf

Milk & Cookies at 4pm, talk to begin at 4:15pm.

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Theory of Computation (ToC) Seminar 2023.

Created by Nathan Higgins Email at Saturday, November 18, 2023 at 2:05 PM.