Authors: Mathieu Roget, Basile Herzog and Giuseppe Di Molfetta
Year: 2020

We propose a new quantum numerical scheme to control the dynamics of a quantum walker in a two dimensional space-time grid. More specifically, we show how, introducing a quantum memory for each of the spatial grid, this result can be achieved simply by acting on the initial state of the whole system, and therefore can be exactly controlled once for all. As example we prove analytically how to encode in the initial state any arbitrary walker’s mean trajectory and variance. This brings significantly closer the possibility of implementing dynamically interesting physics models on medium term quantum devices, and introduces a new direction in simulating aspects of quantum field theories (QFTs), notably on curved manifold.

Authors: Basile Herzog and Giuseppe Di Molfetta
Year: 2020

We provide numerical evidence that the nonlinear searching algorithm introduced by Wong and Meyer \cite{meyer2013nonlinear}, rephrased in terms of quantum walks with effective nonlinear phase, can be extended to the finite 2-dimensional grid, keeping the same computational advantage \BHg{with} respect to the classical algorithms. For this purpose, we have considered the free lattice Hamiltonian, with linear dispersion relation introduced by Childs and Ge \cite{Childs_2014}. The numerical simulations showed that the walker finds the marked vertex in O(N1/4log3/4N) steps, with probability O(1/logN), for an overall complexity of O(N1/4log7/4N). We also proved that there exists an optimal choice of the walker parameters to avoid that the time measurement precision affects the complexity searching time of the algorithm.

Authors: Michael Manighalam and Giuseppe Di Molfetta
Year: 2020

A Plastic Quantum Walk admits both continuous time and continuous spacetime. The model has been recently proposed by one of the authors in \cite{molfetta2019quantum}, leading to a general quantum simulation scheme for simulating fermions in the relativistic and non relativistic regimes. The extension to two physical dimensions is still missing and here, as a novel result, we demonstrate necessary and sufficient conditions concerning which discrete time quantum walks can admit plasticity, showing the resulting Hamiltonians. We consider coin operators as general 4 parameter unitary matrices, with parameters which are function of the lattice step size ε. This dependence on ε encapsulates all functions of ε for which a Taylor series expansion in ε is well defined, making our results very general.

Authors: Pablo Arrighi, Giuseppe Di Molfetta and Nathanaël Eon
Year: 2020

Gauge-invariance is a fundamental concept in Physics—known to provide mathematical justification for the fundamental forces. In this paper, we provide discrete counterparts to the main gauge theoretical concepts directly in terms of Cellular Automata. More precisely, the notions of gauge-invariance and gauge-equivalence in Cellular Automata are formalized. A step-by-step gauging procedure to enforce this symmetry upon a given Cellular Automaton is developed, and three examples of gauge-invariant Cellular Automata are examined.

Authors: Mathieu Roget, Stéphane Guillet, Pablo Arrighi and Giuseppe Di Molfetta
Year: 2020

We provide first evidence that under certain conditions, 1/2-spin fermions may naturally behave like a Grover search, looking for topological defects in a material. The theoretical framework is that of discrete-time quantum walks (QW), i.e. local unitary matrices that drive the evolution of a single particle on the lattice. Some QW are well-known to recover the (2+1)–dimensional Dirac equation in continuum limit, i.e. the free propagation of the 1/2-spin fermion. We study two such Dirac QW, one on the square grid and the other on a triangular grid reminiscent of graphene-like materials. The numerical simulations show that the walker localises around the defects in O(N−−√) steps with probability O(1/logN), in line with previous QW search on the grid. The main advantage brought by those of this paper is that they could be implemented as `naturally occurring’ freely propagating particles over a surface featuring topological—without the need for a specific oracle step. From a quantum computing perspective, however, this hints at novel applications of QW search : instead of using them to look for `good’ solutions within the configuration space of a problem, we could use them to look for topological properties of the entire configuration space.

Authors: Balthazar Casalé, Giuseppe Di Molfetta, Hachem Kadri and Liva Ralaivola
Year: 2020

We consider the quantum version of the bandit problem known as {\em best arm identification} (BAI). We first propose a quantum modeling of the BAI problem, which assumes that both the learning agent and the environment are quantum; we then propose an algorithm based on quantum amplitude amplification to solve BAI. We formally analyze the behavior of the algorithm on all instances of the problem and we show, in particular, that it is able to get the optimal solution quadratically faster than what is known to hold in the classical case.

Authors: Pablo Arrighi, Nicolas Durbec and Aurélien Emmanuel
Year: 2019

Consider a network that evolves reversibly, according to nearest neighbours interactions. Can its dynamics create/destroy nodes?. On the one hand, since the nodes are the principal carriers of information, it seems that they cannot be destroyed without jeopardising bijectivity. On the other hand, there are plenty of global functions from graphs to graphs that are non-vertex-preserving and bijective. The question has been answered negatively—in three different ways. Yet, in this paper we do obtain reversible local node creation/destruction—in three relaxed settings, whose equivalence we prove for robustness. We motivate our work both by theoretical computer science considerations (reversible computing, cellular automata extensions) and theoretical physics concerns (basic formalisms for discrete quantum gravity).

Authors: O. Duranthon and Giuseppe Di Molfetta
Year: 2021

One can think of some physical evolutions as being the emergent-effective result of a microscopic discrete model. Inspired by classical coarse-graining procedures, we provide a simple procedure to coarse-grain color-blind quantum cellular automata that follow Goldilocks rules. The procedure consists in (i) space-time grouping the quantum cellular automaton (QCA) in cells of size N; (ii) projecting the states of a cell onto its borders, connecting them with the fine dynamics; (iii) describing the overall dynamics by the border states, that we call signals; and (iv) constructing the coarse-grained dynamics for different sizes N of the cells. A byproduct of this simple toy-model is a general discrete analog of the Stokes law. Moreover we prove that in the spacetime limit, the automaton converges to a Dirac free Hamiltonian. The QCA we introduce here can be implemented by present-day quantum platforms, such as Rydberg arrays, trapped ions, and superconducting qbits. We hope our study can pave the way to a richer understanding of those systems with limited resolution.

Authors: Kevissen Sellapillay, Pablo Arrighi and Giuseppe Di Molfetta
Year: 2021

We build a quantum cellular automaton (QCA) which coincides with 1+1 QED on its known continuum limits. It consists in a circuit of unitary gates driving the evolution of particles on a one dimensional lattice, and having them interact with the gauge field on the links. The particles are massive fermions, and the evolution is exactly U(1) gauge-invariant. We show that, in the continuous-time discrete-space limit, the QCA converges to the Kogut-Susskind staggered version of 1+1 QED. We also show that, in the continuous spacetime limit and in the free one particle sector, it converges to the Dirac equation, a strong indication that the model remains accurate in the relativistic regime.

Authors: Pablo Arrighi, Marin Costes and Nathanaël Eon
Year: 2021

Gauge symmetries play a fundamental role in Physics, as they provide a mathematical justification for the fundamental forces. Usually, one starts from a non-interactive theory which governs `matter’, and features a global symmetry. One then extends the theory so as make the global symmetry into a local one (a.k.a gauge-invariance). We formalise a discrete counterpart of this process, known as gauge extension, within the Computer Science framework of Cellular Automata (CA). We prove that the CA which admit a relative gauge extension are exactly the globally symmetric ones (a.k.a the colour-blind). We prove that any CA admits a non-relative gauge extension. Both constructions yield universal gauge-invariant CA, but the latter allows for a first example where the gauge extension mediates interactions within the initial CA.

Authors: Amélia Durbec

Year: 2021

We propose a definition of graph subshifts of finite type that extends the power of both subshifts of finite type from classical symbolic dynamics and finitely presented groups from combinatorial group theory. These are sets of (finite or infinite) graphs that are defined by forbidding finitely many local patterns. The definition makes it not obvious to forbid finite graphs, but we prove that some nontrivial subshifts actually contain only infinite graphs: these are built either by forcing aperiodicity (such as in classical constructions of subshifts of finite type on the grid), or no residual finiteness of the period group.

Authors: Pablo Arrighi, Marios Christodoulou, Amélia Durbec
Year: 2020

We provide a robust notion of quantum superpositions of graphs. Quantum superpositions of graphs crucially require node names for their correct alignment, as we demonstrate through a non-signalling argument. Nevertheless, node names are a fiducial construct, serving a similar purpose to the labelling of points through a choice of coordinates in continuous space. We explain that graph renamings are, indeed, a natively discrete analogue of diffeomorphisms. We show how to impose renaming invariance at the level of graphs and their quantum superpositions.

Authors: Pablo Arrighi, Christopher Cedzich, Marin Costes, Ulysse Rémond, Benoît Valiron
Year: 2021

We extend the circuit model of quantum comuptation so that the wiring between gates is soft-coded within registers inside the gates. The addresses in these registers can be manipulated and put into superpositions. This aims at capturing indefinite causal orders, as well as making their geometrical layout explicit. We show how to implement the quantum switch and the polarizing beam splitter within our model. One difficulty is that the names used as addresses should not matter beyond the wiring they describe, i.e. the evolution should commute with “renamings”. Yet, the evolution may act nontrivially on these names. Our main technical contribution is a full characterization of such “nameblind” matrices.