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

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