Abstract: This talk will be split into two parts. First, we study classical oracle separations for the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016). The oracle separation requires lower bounding a certain type of low-depth alternating circuit with some quantum gates. To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest.

Second, we study oracle separations in the quantum oracle model. In recent years, the quantum oracle model has found a lot of use in showing oracle separations between complexity classes and cryptographic primitives. It is generally assumed that proof techniques that do not relativize with respect to quantum oracles will also not relativize with respect to classical oracles. We show that this is not the case: specifically, we show that there is a quantum oracle problem that is contained in the class QMA, but not in a class we call polyQCPH. The class polyQCPH is equal to PSPACE with respect to classical oracles, and it is a well-known result that QMA is contained in PSPACE (also with respect to classical oracles). We believe our findings show the need for some caution when using these non-standard oracle models, particularly when showing separations between quantum and classical resources.

This talk is based on joint works with Shalev Ben-David and Srijita Kundu.

Abstract: In the "search with wildcards'' problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x in {-1,1}^n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(sqrt{n} log n) and a near-matching lower bound of Omega(sqrt{n}). Belovs [Comput.~Comp.'15] subsequently showed a tight O(sqrt{n}) upper bound.

We consider a natural generalization of this problem, parametrized by a subset Q of 2^{[n]}, where an algorithm may test whether x_S = b for an arbitrary S in Q and b in {-1,1}^S of its choice, at unit cost. We show tight bounds for various choices of Q, such as sets of bounded size, contiguous blocks, prefixes, and only the full set. In particular, setting Q = 2^{[n]} recovers the tight bounds mentioned above.

All of these results are derived using a framework that we develop. We show, using the primal adversary bound, that the quantum query complexity of learning x is characterized, up to a constant factor, by a particular abstract analytic optimization program. Based on joint work with Arjan Cornelissen, Subhasree Patro, Nithish Raja, and Swagato Sanyal.

Abstract: Isogenies have emerged as a viable alternative to lattice for post-quantum cryptography over the past 20 years. However, due to the uniquely complex underlying mathematical features and security/efficiency properties, the landscape of isogeny-based cryptography has remained somewhat limited and inaccessible to the wider cryptographic community. Additionally, building new cryptographic applications from isogenies has been a potentially tedious and time-consuming task.

In this talk, I will present overviews of two frameworks for isogeny-based cryptography, namely “cryptographic group actions” and “cryptographic forensic categories”. These frameworks enable viewing isogeny-based cryptography through the lens of abstract and easy-to-understand algebraic structures combined with simple cryptographic hardness assumptions. I will showcase some applications of these frameworks in: (i) enabling simplified expositions of well-known cryptographic constructions from isogenies (e.g., CSIDH-based public-key encryption and the SQIsign family of digital signatures), and (ii) realizing new (plausibly) post-quantum instances of advanced cryptographic primitives from isogenies. I will hope to demonstrate the simplicity and usability of these frameworks for isogeny non-experts. Along the way, I will also talk about some hard problems that form the basis of isogeny-based cryptography, and their classical/quantum hardness as of today.

No prior background in either cryptography or quantum computing will be necessary to follow the talk.

Abstract: A polynomial p(x) is said to approximate a Boolean function f:{0,1}^n -> {0,1} if |f(x)-p(x)| <= 1/3 for all x \in {0,1}^n. The approximate degree of f, denoted adeg(f), is defined to be the minimal degree of an approximating polynomial for f. It was introduced roughly 30 years back in a seminal work of Nisan and Szegedy (Computational Complexity 1994). Since then it has become a powerful and versatile tool in theoretical computer science finding spectacular applications in circuit complexity, quantum query complexity, communication complexity, computational learning, and differential privacy, to name a few.

This talk will be about an important problem about approximate degree -- Does it compose? Formally, for any two Boolean functions f and g, the composed function f o g is defined as, f o g (x_1, ... , x_n) = f(g(x_1), ..., g(x_n)), where x_i \in {0,1}^m. In a beautiful and significant work, Sherstov (Theory of Computing 2013) showed that adeg(f o g) = O(adeg(f)adeg(g)). The approximate degree composition problem posits that this upper bound is tight. That is, adeg(f o g) = \Omega(adeg(f) adeg(g)) for all f and g.

I will survey the current state of progress, including its connections to quantum algorithms.

Qiksit has been a popular software stack for quantum computing, with open surveys indicating 70% of quantum developers across the world using it for a few years now. In this talk, we will discuss the different layers of Qiskit, while exploring some of the key algorithms behind its functioning. We will start with the algorithms used in the core modules which perform efficient compilation of quantum programs. We will then move up the stack to cover a class of sampling-based algorithms that leverage hybrid quantum computing - classical supercomputing infrastructure and provide the state-of-the-art results for many applications of quantum computing. All these have accompanying open-source code in http://github.com/Qiskit to build on them for your research.