Agenda
février
-
10:3011:30
Variational Quantum Algorithms (VQAs) are a leading approach for near-term quantum optimization, with the Quantum Approximate Optimization Algorithm (QAOA) providing a natural bridge to digitized Quantum Annealing (dQA). However, finite circuit depth and noise prevent strictly adiabatic dynamics, motivating the use of Shortcuts to Adiabaticity (STA).
In this seminar, we show STA-inspired extensions of QAOA and analyze their dynamical and resource-theoretic properties. We introduce QAOA-2CD, an improved counterdiabatic formulation that incorporates higher-order corrections from the Baker–Campbell–Hausdorff expansion, yielding a more accurate effective Hamiltonian within a variational framework. We then establish a novel connection between QAOA performance and spectral properties, showing that spectral features influence optimization beyond the regime where QAOA and dQA coincide. Finally, we analyze Trotterization errors in dQA and investigate the evolution of nonstabilizerness as a quantum computational resource.
FrançaisOn Zoom -
14:0014:45
In the first paper of the Graph Minors series [JCTB ’83], Robertson and Seymour proved the Forest Minor theorem: the H-minor-free graphs have bounded pathwidth if and only if H is a forest. In recent years, considerable effort has been devoted to understanding the unavoidable induced substructures of graphs with large pathwidth or large treewidth. In this paper, we give an induced counterpart of the Forest Minor theorem: for any t ⩾ 2, the Kt,t-subgraph-free H-induced-minor-free graphs have bounded pathwidth if and only if H belongs to a class F of forests, which we describe as the induced minors of two (very similar) infinite parameterized families. This constitutes a significant step toward classifying the graphs H for which every weakly sparse H-induced-minor-free class has bounded treewidth. Our work builds on the theory of constellations developed in the Induced Subgraphs and Tree Decompositions series.
This is joint work with Édouard Bonnet and Robert Hickingbotham.
(Benjamin Duhamel) [ENS de Lyon]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .FrançaisLaBRI/178 -
14:4515:45
A triangulation of a surface is k-irreducible if every edge belongs to a non-contractible curve of length k and there are no shorter non-contractible curves. We prove that a k-irreducible triangulation of an orientable surface of genus g has O(k^2g) triangles, which is optimal. This is a factorial improvement in k and a quadratic improvement in g over the previous best bound due to Gao, Richter and Seymour.
This is joint work with Vincent Delecroix and Arnaud de Mesmay.
(Oscar Fontaine) [LaBRI]
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .FrançaisLaBRI/178 -
16:0017:00
Quantum measurements can be used to teleport and process information across entangled states, a paradigm known as measurement-based quantum computing (MBQC). Because quantum operations are inherently error-prone, quantum information can be protected by encoding it in topological error-correcting codes, such as the Toric code. In this talk, we introduce new tools that expand the computational capabilities of topological MBQC while significantly reducing its operational cost. We also explore measurement-induced transitions between short- and long-range entangled phases.
FrançaisOn Zoom -
11:0012:00
Nils Morawietz (LaBRI)
Title: A Parameterized-Complexity Framework for Finding Local Optima
Abstract:
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood. The traditional frameworks, PLS and the standard algorithm problem, introduced by Johnson, Papadimitriou, and Yannakakis (1988) fail to capture the methodology of local search algorithms: PLS is concerned with finding a local optimum and not with using local search, while the standard algorithm problem restricts each improvement step to follow a fixed pivoting rule. In this work, we introduce a novel formulation of local search which provides a middle ground between these models. In particular, the task is to output not only a local optimum but also a chain of local improvements leading to it. With this framework, we aim to capture the challenge in designing a good pivoting rule. Especially, when combined with the parameterized complexity paradigm, it enables both strong lower bounds and meaningful tractability results. Unlike previous works that combined parameterized complexity with local search, our framework targets the whole task of finding a local optimum and not only a single improvement step. Focusing on two representative meta-problems – Subset Weight Optimization Problem with the c-swap neighborhood and Weighted Circuit with the flip neighborhood – we establish fixed-parameter tractability results related to the number of distinct weights, while ruling out an analogous result when parameterized by the distance to the nearest optimum via a new type of reduction.
FrançaisLaBRI 178 -
14:0015:00
TBA
FrançaisLaBRI -
10:4511:45
Tensor networks (TNs) offer powerful algorithms for simulating quantum systems, but struggle to represent states with high entanglement. In contrast, quantum computers naturally accommodate entanglement, though developing efficient quantum algorithms remains an active area of research. Integrating TNs with quantum computing has emerged as a promising strategy to overcome limitations inherent to both classical and quantum approaches. In this talk, we will cover two examples of hybrid TN/quantum algorithms. First, we demonstrate how TNs can enhance the simulation of quantum dynamics on noisy quantum devices. In particular, we use a TN algorithm to compress quantum circuits and show that this approach significantly reduces noise requirements to reach a practical advantage on noisy hardware. Second, we explore how TNs can assist in preparing approximate ground states on quantum computers by optimizing parameterized quantum circuits. We show that carefully selecting TN algorithms enables scaling to large qubit systems and that pre-optimizing circuits offers a promising strategy to avoid barren plateaus by providing warm-start initialization. Finally, we analyze the classical simulation costs of this approach and identify scenarios where quantum computers exhibit favorable scaling.
FrançaisRoom 178 -
14:3015:30
We could expect the first large-scale fault-tolerant quantum computers to be few in number and only accessible to the masses via some sort of cloud service, where users would send computing tasks to remote quantum computers. Under the common belief that quantum computers will be more powerful than classical ones (i.e., that BPP is strictly contained in BQP), this raises the following question : if a quantum computer can efficiently perform a computation that a classical computer cannot, can the classical computer at least efficiently verify its result? Over the years, many techniques have been developed to make delegated quantum computations verifiable classically, using interaction and various assumptions. Notable examples include the protocols of Aharonov, Ben-Or, Eban and Mahadev ( [ https://arxiv.org/abs/1704.04487 | https://arxiv.org/abs/1704.04487 ] ), Broadbent, Fitzsimons and Kashefi ( [ https://arxiv.org/abs/0807.4154 | https://arxiv.org/abs/0807.4154 ] ), and Mahadev ( [ https://arxiv.org/abs/1804.01082 | https://arxiv.org/abs/1804.01082 ] ). However, none of these techniques are known to relativize to oracle problems, some of which provably separate BPP and BQP and aren't trivially verifiable by a classical agent.
In this talk, I will introduce the first ever protocols for some of these oracle problems, namely Simon's problem and the Forrelation problem, by adapting known verification techniques in novel ways. I will also discuss the possibility of the existence of an oracle problem that is efficiently solvable by a quantum computer, but for which there couldn't exist a verification protocol between a quantum prover and a classical verifier. This talk is based on results from my PhD thesis, which are yet unpublished.
FrançaisOn Zoom -
13:0014:00FrançaisLaBRI, salle 178