Quantum Information Workshop (April 2025)

Date: Monday, April 7, 2025
Place: Ruhr University Bochum, Building MC, Room 1.84 (see here for directions)

We are organizing a half-day workshop, with a fantastic set of speakers, covering recent directions in quantum information and computing. Please contact Levent if you are interested in attending.

Schedule

Abstracts

Dmitry Grinko, High-dimensional quantum Schur transforms

Schur-Weyl duality—a fundamental result in representation theory—has greatly impacted quantum information, from quantum state tomography to the recent simple construction of linear-depth unitary t-designs and pseudorandom unitaries.

Its algorithmic manifestation as a quantum circuit for the Schur transform was initially described by Bacon, Chuang and Harrow (BCH) in 2004. Schur transform unitary maps the computation basis of n qudits, each of local dimension d, to a Schur basis, which is naturally suited for the representation theory of unitary and symmetric groups. BCH construction is based on the sequential application of the Clebsch-Gordan transforms, and its total gate complexity is poly(n,d). Famously, Aram Harrow’s PhD thesis contains a footnote in which he conjectures the existence of poly(n, log(d)) realisation of the Schur transform. However, the details have never been worked out. More recently, in 2018, Hari Krovi constructed a Schur transform from the point of view of symmetric group representation theory based on the known circuit for the Quantum Fourier Transform of the symmetric group, first outlined by Robert Beals in 1997. A very nice feature of Krovi’s approach is that the resulting quantum circuit has complexity poly(n, log(d)) “automatically”. Unfortunately, a mistake was found recently in one of the steps of Krovi’s algorithm, putting the existence of the only known efficient high-dimensional Schur transform at risk. In my talk, among other things, I will explain how we fixed this mistake. Moreover, in the process, we made the original BCH construction efficient in the local dimension d, thus confirming Harrow’s conjecture.

Maris Ozols, From dynamic programming to quantum groups

There will be no new results in this talk. Instead, I will take you on a stroll through three areas of mathematics - combinatorics, representation theory, and quantum computing - and tell you a story about connections between them. The main characters in this story are: dynamic programming, RSK correspondence, Schur transform, q-deformation, and matrix quantum groups.

Benjamin Lovitz, Nearly tight bounds for testing tree tensor network states

Tree tensor network states (TTNS) form a class of physically motivated quantum states. We study the task of testing TTNS in the property testing framework, wherein one is handed multiple copies of an unknown quantum state, and performs measurements to determine whether the state forms a TTNS (of a given bond dimension) or is epsilon-far from TTNS. The minimum number of copies required is called the copy complexity of the task. We prove nearly tight bounds on the copy complexity of testing TTNS. This generalizes prior works on testing matrix product states (MPS), and closes a gap left in these works. Based on joint work with Angus Lowe.

Seyoon Ragavan, The Jacobi Factoring Circuit: Classically Hard Factoring in Sublinear Quantum Space and Depth

In this talk, we present a compact quantum circuit for factoring n-bit integers of the form P^2 Q. When log Q = O(n^a) for 2/3 < a < 1, the space and depth of this circuit are sublinear in n (specifically, Otilde(log Q)) and the number of gates is Otilde(n); at the same time, no known classical algorithms exploit the relatively small size of Q to run asymptotically faster than general-purpose factoring algorithms. To our knowledge, this is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem. We thus believe that factoring such numbers has potential to be the most concretely efficient classically-verifiable proof of quantumness currently known.

Our circuit builds on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du, and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of A mod B, in the regime where B is classical and much larger than A. Finally, we note that our circuit for computing the Jacobi symbol generalizes to related problems such as computing the greatest common divisor and modular inverses, and thus could be of independent interest.

Joint work with Gregory D. Kahanamoku-Meyer, Vinod Vaikuntanathan, and Katherine Van Kirk: 2412.12558.

Galina Pass, Multidimensional Quantum Walks, Recursion, and Quantum Divide & Conquer

We introduce an object called a subspace graph that formalizes the technique of multidimensional quantum walks. Composing subspace graphs allows one to seamlessly combine quantum and classical reasoning, keeping a classical structure in mind, while abstracting quantum parts into subgraphs with simple boundaries as needed. As an example, we show how to combine a switching network with arbitrary quantum subroutines, to compute a composed function. As another application, we give a time-efficient implementation of quantum Divide & Conquer when the sub-problems are combined via a Boolean formula. We use this to quadratically speed up Savitch’s algorithm for directed st-connectivity.

Vincent Steffan, Logical operators and fold-transversal gates bivariate bicycle codes