IQC Math and CS seminar featuring Dale Jacobs

The Space Just Above One Clean Qubit

by Dale Jacobs | Tufts University

Consider the model of computation where we start with two halves of a 2n-qubit maximally entangled state, apply a universal quantum circuit to one half, measure both halves at the end, and perform classical postprocessing. This model, which we call 1/2BQP, was introduced in STOC 2017 [AKBM], and can be viewed as a generalization of the one-clean-qubit model (DQC1) where we learn the content of a high entropy input state only after the computation is completed.

In this talk, I will present strong evidence that 1/2BQP has computational power strictly between DQC1 and BQP. In particular, 1/2BQP can simulate IQP computations, solve oracle problems such as Simon’s problem, Forrelation, and Period Finding, and implement Shor’s algorithm for Order Finding and Factoring outside of the oracle setting.

Furthermore, 1/2BQP is strictly weaker than BQP relative to an oracle, and cannot obtain the quadratic speedup for unstructured search given by Grover’s algorithm. I will also highlight several open problems.

Location

• QNC 3206

• Online on Zoom

  • Meeting ID: 942 3517 8833

  • Passcode: 255863