Uttam
Singh
CTP PAS
An important theoretical problem in the study of quantum computation, that is also practically relevant in the context of near-term quantum devices, is to understand the computational power of hybrid models that combine polynomial-time classical computation with short-depth quantum computation. Here, we consider two such models: CQ_d which captures the scenario of a polynomial-time classical algorithm that queries a 𝑑-depth quantum computer many times; and QC_d which is more analogous to measurement-based quantum computation and captures the scenario of a 𝑑-depth quantum computer with the ability to change the sequence of gates being applied depending on measurement outcomes processed by a classical computation. Chia, Chung and Lai (STOC 2020) and Coudron and Menda (STOC 2020) showed that these models (with 𝑑 = log^O(1) (𝑛)) are strictly weaker than BQP (the class of problems solvable by polynomial-time quantum computation), relative to an oracle, disproving a conjecture of Jozsa in the relativised world. In this talk, we will show that, despite the similarities between CQ_d and QC_d, the two models are incomparable, i.e. CQ_d is not a subset or whole set QC_d and QC_d is not a subset or whole set CQ_d relative to an oracle. In other words, we show that there exist problems that one model can solve but not the other and vice versa.
________________________________
Zoom meeting details
Topic: Quantum Information and Quantum Computing Working Group Seminar
Time: Wednesday, 09.02.2022, 15:15 Warsaw (CET)
Join Zoom Meeting
https://tinyurl.com/quantun-cft
Meeting ID: 87850698108
Passcode: quantin
If you encounter any problems with connecting to the Zoom meeting, please email calegari@cft.edu.pl.
