Agenda
février
-
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 -
10:0013:00
L'énumération des chemins dans des réseaux est un sujet central en combinatoire énumérative. En particulier, l'étude des chemins prenant des pas dans un ensemble admissible fini, et contraints dans une certaine région a fait l'objet d'un effort soutenu les vingt dernières années, prolongeant l'exemple historique des chemins de Dyck. Notamment, l'usage systématique des équations aux variables catalytiques pour traiter ce problème permet d'appliquer de nombreuses techniques provenant de combinatoire énumérative, de calcul formel, de théorie des probabilités, d’analyse ou de théorie de Galois aux différences, afin de classifier les séries génératrices de tels chemins selon une hiérarchie algébro-différentielle. Cette collaboration a mené à une première classification remarquable des séries génératrices de chemins issus de modèles à petits pas, initiée par les travaux de Fayolle, Iasnogorodski et Malyshev, et d'autre part de Bousquet-Mélou et Mishna, et complétée par de nombreux autres auteurs issus des disciplines susnommées. Depuis, de nombreux efforts ont été menés pour étendre les outils de cette première classification afin de traiter des cas plus complexes. C’est dans ce contexte que s’inscrit la thèse, construite autour de deux extensions différentes, la première concernant les modèles à grands pas, la seconde concernant les chemins à bords interactifs.
-
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:0015:00
TBA
FrançaisLaBRI -
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
-
09:0010:00
Most of the quantum algorithms have been developed using a finite set of universal quantum gates, which allows for an easy decomposition of any unitary transformation. However, this set of gates includes entangling two-body gates. In the current context of faulty devices, the near-term noisy intermediate-scale quantum era, implementing these gates is deemed costly, both because the time requirement to implement these operations is much larger than for the single-qubit gates, and because they are more susceptible to errors. In contrast to the digital paradigm, analog quantum computers do not allow for arbitrary operations. But in turn of its lack of flexibility, analog devices excel in their robustness and resilience against noise.
In this context, digital-analog quantum computing (DAQC) was proposed as a way of taking advantage of the robustness of analog quantum computers while maintaining the flexibility of digital quantum computing. For this, this paradigm employs the natural interaction Hamiltonian of the devices as a resource for the entangling operations. Then, universality can be reached by the application of arbitrary single qubit gates. This allows us to implement any desired operation without the need of employing expensive and noisy two-qubit gates.
Here I present the contributions to the state of the art made during my PhD. In particular, I will describe the solution to one of the main challenges of DAQC, that was achieving universality employing efficient constructive methods. While optimal DAQC protocols require tackling an NP-Hard problem, we have proposed suboptimal protocols which only require polynomial classical resources to be calculated. In addition to this, we further studied its noise resilience, and introduced error mitigation techniques specifically designed for this paradigm. We further continued on the implementation of various algorithms and simulation tasks, showing the possibility that DAQC offers a valid alternative which in some cases might provide advantages in their run-time or fidelity.
FrançaisLaBRI