Agenda
janvier
-
14:0015:00
We will look at an analogue theorem of the classical Erdős-Pósa Theorem. We prove a $GF(q)$-representable matroid analogue of Robertson and Seymour's theorem that planar graphs have an Erdős-Pósa property. Given a matroid $N$, we prove that for every matroid $M$ with bounded branch width, $M$ either contains $r$ skew copies of $N$, or there is a small perturbation of $M$ that doesn't contain $N$ as a minor.
This is joint work with James Davies and Meike Hatzel.
(Fernanda Rivera Omana) [University of Waterloo]
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
février
-
11:0012:00
Jonathan Narboni
Title: Lower Bound for Constant-Size Local Certification
Abstract:
Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct. The quality of a certification is measured by the size of its labels: the smaller, the better. This notion plays a central role in self-stabilization, because the size of the certification is a lower bound (and often an upper bound) on the memory needed for silent self-stabilizing construction of distributed data structures.
When it comes to the size of the certification labels, one can identify three important regimes: the properties for which the optimal size is polynomial in the number of vertices of the graph, the ones that require only polylogarithmic size, and the ones that can be certified with a constant number of bits. The first two regimes are well studied, with several upper and lower bounds, specific techniques, and active research questions. On the other hand, the constant regime has never been really explored.
The main contribution of this paper is the first non-trivial lower bound for this low regime. More precisely, we show that by using certification on just one bit (a binary certification), one cannot certify k-colorability for k≥3. To do so, we develop a new technique, based on the notion of score, and both local symmetry arguments and a global parity argument. We hope that this technique will be useful for establishing stronger results.
We complement this result with an upper bound for a related problem, illustrating that in some cases one can do better than the natural upper bound.
FrançaisLaBRI 178 -
14:3015:30
Scientific computing problems in physics, chemistry, and engineering—such as the solution of large-scale linear systems, the simulation of dynamical equations, and spectral analysis—pose fundamental challenges for classical algorithms as system sizes grow. Quantum computing offers a promising avenue for addressing these challenges by exploiting quantum-mechanical resources to accelerate key computational primitives. This talk presents completed and ongoing thesis work on quantum algorithms for scientific computation. The first part focuses on Hamiltonian simulation viewed as a structured class of ordinary differential equations. We review product-formula methods, highlighting their strengths and limitations, and contrast them with asymptotically optimal approaches based on qubitization. Recent advances in multi-product formulas are then presented, showing how commutator scaling can be rigorously leveraged to achieve near-optimal dependence on both simulation time and target precision. The second part addresses quantum algorithms for Fourier analysis. In particular, we discuss a quantum algorithm for the non-uniform quantum Fourier transform, implemented using parametrized quantum circuits and quantum signal processing techniques. The talk concludes with brief remarks on ongoing work and directions for future research.
FrançaisOn Zoom -
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: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