Discussions on Septembet 11 2021

I appraised Srik and Ara about my reading of the paper Oracle Quantum Computing by Andre Berthiaume and Gilles Brassard. I found that oracles are useful in showing strict inclusion. However Srik wanted to know the difference between partial evidence provided by oracles and complete evidence required for non-relativized separation of complexity classes. I plan to investigate it in the following week. Also, it struck to me, what if we can use revitalization in generalized probabilistic theories.

The context of Raz and Tal is - P is contained in NP is contained in PH is contained in PSPACE. And P is contained in BPP is contained in BQP is contained in PSPACE. So, BQP is contained somewhere between P and PSPACE, however its exact placement is open. Scott gave a efficient quantum algorithm for distinguishing uniform distribution from forrelation so this problem is in BQP. Raz and Tal shows that this distinguishability problem is not solvable by AC0 circuits. It is known that AC0 is equivalent to PH. And hence forrelation is not in PH. Thus, BQP is not completely contained in PH with respect to some oracle. The proof is a relativized proof.  

I am using the following resources to study Raz and Tal result 

• https://www.youtube.com/watch?v=L5wTIPQlhCI
• https://www.youtube.com/watch?v=wjJVamcXB7o
• https://www.tandfonline.com/doi/abs/10.1080/09500349414552351
  

Srik also suggested if Feynman's approach has some computational analogy. It appeared to me that there might be a parallel between Feynman's approach and configuration graph of a non-deterministic Turing machine. The matter needs more pondering.

Then we deliberated on the possible techniques used in complexity theory. It appeared to me (from some introductory understanding) diagonalization plays a important role. Srik wanted to know if "forcing" is used in complexity.

I wanted to know about the focus that we needed to maintain to keep us on track. Srik suggested that we can explore - (i) oracles in GPT (ii) relativizations in GPT. Ara added that I should take up around five papers in the line of urmila mahadevan, raz and tal etc. and focus on forrelations. He reasoned that forrelations are intriguing, may lead to development of better algorithms; we can also explore applications of forrelations as its still an open question. Overall, Ara intends to view forrelations from quantum foundations perspective.

Ara also pointed out that mathematical techniques required in complexity proofs are involved and we must be cautious before delving solely on it. And I completely concur with his suggestion, complexity theory is involved mathematically. But at the same time, once understood, the insights are tremendous, in fact it gives a new way to see and access our understanding of reality.

Ara also suggested that, focusing on forrelations may lead to few short research papers.

We also discussed in the passing some problems (pointed by Ara) like random circuit sampling, equivalence of hamiltonian complexity to QMA, spin glass ground state, matrix mortality problem, quantumness of single quantum systems. 

The most important people in this seemed to be vazirani, aronson, ambainis, watrous, sha-lev ben-david, ronald de wolf, barrett and lee.