Research Interaction Team on Quantum Information

Fall 2017 Spring 2018 Fall 2018 Fall 2020


(See also: The IQC-QuICS Math and Computer Science Seminar.)


Organizers: Carl Miller, Yusuf Alnawakhtha

In this seminar, we are interested in all aspects of research at the intersection between quantum information science and mathematics.  Goals for talks include:

·      Studying recent research results in quantum information from a mathematical angle;

·      Finding examples (old and new) in which existing tools from mathematics can be adapted for application in quantum information;

·      Studying quantum algorithms for mathematical problems.


This seminar is associated with QuICS and the UMD math department.  Participation from other departments is encouraged.  Graduate students can sign up for the seminar for credit (as MATH 689).


All meetings are online.  Our weekly time slot is Monday, 2:00-3:00pm.



Previous Meetings

Time: Monday, August 31st, 2020, 2:00-3:00pm.
Title: Organizational meeting.
Speaker: Carl Miller
Abstract: We will discuss logistics and possible research themes for the coming semester.



Time: Monday, September 14th, 2020, 2:00-3:00pm.
Title: Pictorial Proofs Using ZX-Calculus
Speaker: Yusuf Alnawakhtha

Abstract: In this talk, we will briefly explore the use of monoidal categories in quantum information. Namely we will introduce the ZX-Calculus which is a diagrammatic formalism that strives to enhance intuition by providing pictorial proofs and we will provide examples of how some proofs can be simplified using this framework. Later in the talk, we will go over a recent application of ZX-Calculus in fault tolerant quantum computing and how it was used to provide the intuition for this result.


[1] Coecke, Bob. "Quantum picturalism." Contemporary physics 51.1 (2010): 59-83.
[2] de Beaudrap, Niel, Xiaoning Bian, and Quanlong Wang. "Fast and effective techniques for T-count reduction via spider nest identities." arXiv preprint arXiv:2004.05164 (2020).


Time: Monday, September 21st, 2020, 2:00-3:00pm.
Title: Quantum randomness and the geometry of the Schatten matrix norm

Speaker: Carl Miller

Abstract: One of the most successful recent applications of quantum information has been the generation of "certified" random numbers.   The unique properties of quantum devices allow the generation of numbers that are provably random, offering a potential major benefit to cryptography and other fields.  Constructing the right theory to prove quantum randomness can be challenging.  Quantum devices and adversaries are modeled by complex vector spaces whose dimensions may be arbitrarily large, and proving security in such a setting leads to some difficult mathematical problems.  This talk will be a retrospective look at one successful approach to quantum randomness that is based on the convexity of the Schatten matrix norm.


C. Miller, Y. Shi.  “Universal security for Randomness Expansion from the Spot-Checking Protocol.”  SIAM Journal on Computing 46(4), 1304-1335 (2017).


Time: Monday, October 5th, 2020, 2:00-3:00pm.
Title: Symmetries, graph properties, and quantum speedups
Speaker: Daochen Wang

Abstract: Aaronson and Ambainis (2009) and Chailloux (2018) showed that fully symmetric (partial) functions do not admit exponential quantum query speedups. This raises a natural question: how symmetric must a function be before it cannot exhibit a large quantum speedup?
In this work, we prove that hypergraph symmetries in the adjacency matrix model allow at most a polynomial separation between randomized and quantum query complexities. We also show that, remarkably, permutation groups constructed out of these symmetries are essentially the only permutation groups that prevent super-polynomial quantum speedups. We prove this by fully characterizing the primitive permutation groups that allow super-polynomial quantum speedups.
In contrast, in the adjacency list model for bounded-degree graphs (where graph symmetry is manifested differently), we exhibit a property testing problem that shows an exponential quantum speedup. These results resolve open questions posed by Ambainis, Childs, and Liu (2010) and Montanaro and de Wolf (2013)


Reference: Ben-David, S., Childs, A. M., Gilyén, A., Kretschmer, W., Podder, S., & Wang, D. (2020). Symmetries, graph properties, and quantum speedups. arXiv preprint arXiv:2006.12760.

Time: Monday, October 19th, 2020, 2:00-3:00pm.
Title: Quantum Query Complexity of Symmetric Oracle Problems
Speaker: Shih-Han Hung
Abstract: In this talk, I will present quantum query complexity of symmetric oracle problems. In particular, we will be exploring the query complexity of quantum learning problems in which the oracles form a group G of unitary matrices, and a description of the optimal success probability of a t-query quantum algorithm in terms of group characters. More generally, in the coset identification problem, for a subgroup H of group G, the task is to determine which coset the group element belongs to. The authors provide character-theoretic formulas for the optimal success probability achieved by a t-query algorithm for this problem. It generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation.


[1] Daniel Copeland, James Pommersheim, Quantum query complexity of symmetric oracle problems,
[2] Orest Bucicovschi, Daniel Copeland, David A. Meyer, and James Pommersheim. Single-query quantum algorithms for symmetric problems,

Time: Monday, November 9th, 2020, 2:00-3:00pm.
Title: Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle).
Speaker: Matthew Coudron
Abstract: A conjecture of Jozsa (arXiv:quant-ph/0508124) states that any polynomial-time quantum computation can be simulated by polylogarithmic-depth quantum computation interleaved with polynomial-depth classical computation. Separately, Aaronson conjectured that there exists an oracle O such that BQP^O ≠ (BPP^(BQNC))^O. These conjectures are intriguing allusions to the unresolved potential of combining classical and low-depth quantum computation. In this work we show that the Welded Tree Problem, which is an oracle problem that can be solved in quantum polynomial time as shown by Childs et al. (arXiv:quant-ph/0209131), cannot be solved in BPP^(BQNC), nor can it be solved in the class that Jozsa describes. This proves Aaronson's oracle separation conjecture and provides a counterpoint to Jozsa's conjecture relative to the Welded Tree oracle problem. More precisely, we define two complexity classes, HQC and JC whose languages are decided by two different families of interleaved quantum-classical circuits. HQC contains BPP^(BQNC) and is therefore relevant to Aaronson's conjecture, while JC captures the model of computation that Jozsa considers. We show that the Welded Tree Problem gives an oracle separation between either of {JC, HQC} and BQP. Therefore, even when interleaved with arbitrary polynomial-time classical computation, greater "quantum depth" leads to strictly greater computational ability in this relativized setting.


Coudron, M., & Menda, S. (2020). Computations with greater quantum depth are strictly more powerful (relative to an oracle).

Time: Monday, December 7th, 2020, 2:00-3:00pm.
Title: Bounding the Accuracy of Distributed Quantum Sensing
Speaker: Jessica Thompson
Abstract: A potential application of quantum information is to distributed sensing. The goal of a sensing problem can be described as calculating a specific value by measuring signals with a collection of sensors. With a classical signal, the accuracy in which the quantity can be determined is inversely bounded by the square root of the number of sensors; this bound is called the standard quantum limit. However, the use of quantum resources, such as entanglement and squeezed light, allows one to surpass this limit. For specific protocols, the accuracy is bounded by the quantum Cramér-Rao bound, which relies on the quantum Fisher Information of the system. In this talk, we will discuss the various quantum protocols for distributed quantum sensing and the calculation of this bound, in regards to their accuracy.


[1] Zhuang, Quntao, Zheshen Zhang, and Jeffrey H. Shapiro. "Distributed quantum sensing using continuous-variable multipartite entanglement." Physical Review A 97.3 (2018): 032329.
[2] Liu, Jing, et al. "Quantum Fisher information matrix and multiparameter estimation." Journal of Physics A: Mathematical and Theoretical 53.2 (2019): 023001.




J. Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.


S. Wehner, D. Elkouss, R. Hanson.  Quantum internet: A vision for the road ahead.  Science 362, Issue 6412 (2018).


National Academies of Sciences, Engineering, and Medicine.  Quantum Computing: Progress and Prospects.  The National Academies Press, 2019.  (Available here – online version is free.)