Monday May 30
14:00 Sergii Strelchuk ( Cambridge )
Superexponential quantum advantage and fast learning of quantum states using group equivariant convolutional quantum ansätze
TBA
14:40 Sander Gribling ( UPDiderot / IRIF )
Quantum algorithms for matrix scaling and balancing
In this talk I will give an overview of recent work on quantum algorithms and lower bounds for the matrix scaling (and matrix balancing) problems. The matrix scaling problem asks to find positive weights, aka scaling factors, for each of the rows and columns of a nonnegative matrix in such a way that the rescaled matrix has row- and column-sums equal to some prescribed vectors. Classical algorithms can solve this problem in near-linear time. We show that quantum algorithms can do so in sub-linear time in the low-precision regime. We prove that in that regime our algorithms are optimal (up to the exponent in the polynomial-error dependency). Moreover, we show that in the high-precision regime quantum algorithms can not do significantly better than classical algorithms.
15:20 Dmitry Grinko (CWI / UvA)
Linear programming with unitary-equivariant constraints
Unitary equivariance is a natural symmetry that occurs in many contexts in physics and mathematics. Optimization problems with such symmetry can often be formulated as semidefinite programs for a $latex d^{p+q}$-dimensional matrix variable that commutes with $latex U^{p} \otimes \bar{U}^{q}$, for all $latex U \in \mathcal{U(}d)$. Solving such problems naively can be prohibitively expensive, especially when the local dimension $latex d$ is large. We show that, under additional symmetry assumptions, this problem reduces to linear programming and we provide a general framework for solving such programs in time that does not scale in $latex d$. Our approach uses a compact parameterization of the solution space by diagrammatically expressed walled Brauer algebra idempotents. We expect our methods to extend to general unitary-equivariant semidefinite programs.
16:10 Nikhil Mande ( CWI / UvA )
Improved Quantum Query Upper Bounds Based on Classical Decision Trees
In the first part of this talk we will discuss the notion of rank of decision trees, which is essentially the largest depth of a complete subtree embedded in the initial tree. We observe the equivalence of rank and “guessing complexity,” a measure of decision trees used by Lin and Lin [Theory of Computing’16] and Beigi and Taghavi [Quantum’20] to give upper bounds on quantum query complexity of functions based on classical query algorithms for them.
In the second part of the talk we will first note that the best speed-up obtainable using the approach of Beigi and Taghavi is captured by a polynomial optimization program on assignments of real weights to edges of the underlying classical decision tree. We then give a recursive expression for the optimal solution to this program and bound the optimum from above in terms of natural measures of the decision tree.
16:50 Simon Apers ( UPDiderot / IRIF )
Cut query algorithms with star contraction
“We study the complexity of determining the edge connectivity of a simple graph with cut queries. We show that (i) there is a bounded-error randomized algorithm that computes edge connectivity with $latex O(n)$ cut queries, and (ii) there is a bounded-error quantum algorithm that computes edge connectivity with $latex \tilde O(\sqrt{n})$ cut queries. To prove these results we introduce a new technique, called \emph{star contraction}, to randomly contract edges of a graph while preserving non-trivial minimum cuts. The $latex O(n)$ bound from item (i) was not known even for the simpler problem of connectivity. The bound is tight under the reasonable conjecture that the randomized communication complexity of connectivity is $latex \Omega(n \log n)$, an open question since the seminal work of Babai, Frankl, and Simon [FOCS’86]. The quantum algorithm from item (ii) gives a nearly-quadratic separation with the randomized complexity, and addresses an open question of Lee, Santha, and Zhang [SODA’21]. The algorithm can alternatively be viewed as computing the edge connectivity of a simple graph with $latex \tilde O(\sqrt{n})$ matrix-vector multiplication queries to its adjacency matrix.”
Tuesday May 31
09:00 Patrick Gelß ( ZIB )
Low-rank tensor representations of quantum circuits
Quantum computing is arguably one of the most revolutionary and disruptive technologies of this century. Due to the ever-increasing number of potential applications as well as the continuing rise in complexity, the development, simulation, optimization, and physical realization of quantum circuits is of utmost importance for designing novel algorithms. We show how matrix product states (MPSs) and matrix product operators (MPOs) can be used to express not only the state of the system but also quantum gates and entire quantum circuits as low-rank tensors. This allows us to analyze and simulate complex quantum circuits on classical computers and to gain insight into the underlying structure of the system. We present different examples to demonstrate the advantages of MPO formulations and provide a new perspective on the construction of quantum algorithms.
09:40 Romy Minko ( Bristol )
Improved Methods for Gate Approximation
In this talk, I shall discuss a novel method for solving the General Unitary Approximation problem, that is, given a target unitary U, and a finite universal gate set G, find a sequence of elements from G that approximates U. This method was inspired by the cryptanalysis of the CGL hash function. Further, I shall discuss how approximation with convex combinations of channels admits a quadratic improvement in the accuracy parameter for a number of problems.
10:50 Mitchell Chiew ( Cambridge )
Optimal fermion-qubit mappings
Simulating fermionic systems on a quantum computer requires a high-performing mapping of fermionic states to qubits. We introduce a novel way to optimise fermion-qubit mappings without expending any additional resources. Our method involves strategically numbering fermions according to their interaction Hamiltonian: for fermions interacting in a square lattice, this leads to simulation circuits with terms using 13.9% less gates than in previous methods. By adding only two ancilla qubits we can reduce the average gate count of Hamiltonian terms by 37.9% compared to previous methods. We also find efficient enumeration designs for a range of other practical connectivities.
11:30 Wilfred Salmon ( Cambridge )
Optimality of measurements in Quantum Metrology
In Quantum Metrology, the Quantum Fisher Information has been well studied as the metric of asymptotic information content of a parameterised quantum state. However, in the non-asymptotic regime, biased estimation strategies are not well understood. We present a strong notion of optimality of a measurement, and then prove that a parameterised state has an optimal measurement if and and only if it is classical.
14:00 Adrian Vladu ( UPDiderot / IRIF )
TBA
TBA
14:40 Miklos Santha ( UPDiderot / IRIF )
Classical and quantum algorithms for variants of Subset-Sum via dynamic programming
TBA
15:20 El Amine Cherrat ( UPDiderot / IRIF )
Quantum Reinforcement Learning via Policy Iteration
We provide a general framework for performing quantum reinforcement learning via policy iteration. We validate our framework by designing and analysing: quantum policy evaluation methods for infinite horizon discounted problems by building quantum states that approximately encode the value function of a policy and quantum policy improvement methods by post-processing measurement outcomes on these quantum states.
16:10 Paula Belzig ( UCPH )
Fault-tolerant coding for the entanglement-assisted classical capacity
The process of communicating information between two devices, a sender and a receiver, is modelled by a noisy channel which maps an encoded message to a potentially corrupted output signal. Then, the capacity of a given channel quantifies the optimal asymptotic rate of sending information over the channel such that the original message can always be recovered. Usually, the study of capacities assumes that the circuits which the sender and the receiver use for encoding and decoding the information consist of perfect gates without noise. However, this is not believed to be true for quantum devices manufactured in the near-term and even long-term future. Assuming that each gate is affected by an error with probability, we use techniques from fault-tolerant quantum computing to prove coding theorems for a fault-tolerant version of entanglement-assisted classical capacity, devising a coding technique for a fault-tolerant version of this type of capacity and proving in particular that it approaches the usual, fault-less case for vanishing gate error probability.
16:50 Andreas Bluhm ( UCPH )
Position-based cryptography: Single-qubit protocol secure against multi-qubit attacks
While it is known that unconditionally secure position-based cryptography is impossible both in the classical and the quantum setting, it has been shown that some quantum protocols for position verification are secure against attackers which share a quantum state of bounded dimension. In this work, we consider the security of two protocols for quantum position verification that combine a single qubit with classical strings of total length 2n: The qubit routing protocol, where the classical information prescribes the qubit’s destination, and a variant of the BB84-protocol for position verification, where the classical information prescribes in which basis the qubit should be measured. We show that either protocol is secure for a randomly chosen function if each of the attackers holds at most n/2−5 qubits. With this, we show for the first time that there exists a quantum position verification protocol where the ratio between the quantum resources an honest prover needs and the quantum resources the attackers need to break the protocol is unbounded. The verifiers need only increase the amount of classical resources to force the attackers to use more quantum resources. Concrete efficient functions for both protocols are also given — at the expense of a weaker but still unbounded ratio of quantum resources for successful attackers. Finally, we show that both protocols are robust with respect to noise, making them appealing for applications.
Wednesday June 1
09:00 Yanlin Chen ( CWI / UvA )
Quantum algorithms and lower bounds for linear regression with norm constraints
Lasso and Ridge are important minimization problems in machine learning and statistics. They are versions of linear regression with squared loss where the vector $latex \theta\in\mathbb{R}^d$ of coefficients is constrained in either $latex \ell_1$-norm (for Lasso) or in $latex \ell_2$-norm (for Ridge). We study the complexity of quantum algorithms for finding $latex \epsilon$-minimizers for these minimization problems. We show that for Lasso we can get a quadratic quantum speedup in terms of d by speeding up the cost-per-iteration of the Frank-Wolfe algorithm, while for Ridge the best quantum algorithms are linear in $latex d$, as are the best classical algorithms.
09:40 Stacey Jeffery ( CWI / UvA )
Quantum walks for k-distinctness
We present a new quantum walk technique and apply it to the problem of k-distinctness. A previous result of Belovs gave an upper bound on the quantum query complexity for this problem (for any constant k), but no matching time bound was given. To see if we achieve this matching time bound, you’ll have to attend my talk.
10:50 Maksims Dimitrijevs ( LU )
Implementation of a quantum walk on a tree and DAG size estimation algorithms for real quantum computers
In this research, we focus on the implementation of quantum algorithms to investigate their behavior. First, we implement an algorithm for a quantum walk on a tree proposed by Ashley Montanaro, that allows to improve the search on a tree that is generated by backtracking algorithm. Next, we implement an algorithm for DAG size estimation by Andris Ambainis and Martins Kokainis. For both algorithms we investigate the capacity of currently available quantum computers and limitations of local simulators (running experiment on a local computer). We also analyze the outputs of algorithms and conclude that in some cases output of algorithm can reveal additional information on the structure of the solution for problem.
During the talk, we will show and explain some details of implementation of algorithms and discuss the outcomes of our experiments.
Algorithms that we implemented are described in the following papers: https://arxiv.org/abs/1509.02374, https://arxiv.org/abs/1704.06774v2.
11:30 Leonardo Novo ( ULB )
Quadratic speedup for spatial search by continuous-time quantum walk
Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this article, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analog procedure to perform operations on a state of the form $latex e^{-tH^2}\left|\psi\right\rangle$, for a given Hamiltonian $latex H$: it only requires evolving $latex H$ for time scaling as $latex \sqrt{t}$.
This allows us to quadratically fast-forward the dynamics of a continuous-time classical random walk. The applications of our work thus go beyond the realm of quantum walks and can lead to new analog quantum algorithms for preparing ground states of Hamiltonians or solving optimization problems.