Alain Sarlette
email: alain.sarlette@ugent.be

Pierre Rouchon
email: pierre.rouchon@mines-paristech.fr

Robust open-loop stabilization of Fock states by time-varying quantum interactions ⋆

Keywords: open-loop control systems, discrete-time, Lyapunov function, stabilization methods, photons, physics, Hilbert spaces

A quantum harmonic oscillator (spring subsystem) is stabilized towards a target Fock state by reservoir engineering. This passive and open-loop stabilization works by consecutive and identical Hamiltonian interactions with auxiliary systems, here three-level atoms (the auxiliary ladder subsystem), followed by a partial trace over these auxiliary atoms. A scalar control input governs the interaction, defining which atomic transition in the ladder subsystem is in resonance with the spring subsystem. We use it to build a time-varying interaction with individual atoms, that combines three non-commuting steps. We show that the resulting reservoir robustly stabilizes any initial spring state distributed between 0 and 4n + 3 quanta of vibrations towards a pure target Fock state of vibration number n. The convergence proof relies on the construction of a strict Lyapunov function for the Kraus map induced by this reservoir setting on the spring subsystem. Simulations with realistic parameters corresponding to the quantum electrodynamics setup at Ecole Normale Supérieure further illustrate the robustness of the method.

INTRODUCTION

The last decades have seen a surge of developments on the control of systems that feature essential quantum dynamics (see e.g. [START_REF] Wiseman | Quantum Measurement and Control[END_REF]). A major motivation is to harness their peculiar possibilities for IT applications ranging from fundamentally-secure communication, over hyper-precise measurements, to the quantum computer (see e.g. [START_REF] Nielsen | Quantum computation and quantum information[END_REF], [START_REF] Haroche | Exploring the quantum: atoms, cavities and photons[END_REF]). A basic building block for operations with quantum dynamics is the ability to produce and stabilize a wealth of different 'target' states. The extreme fragility, limited measurement and control possibilities in quantum systems make this already a challenging task for many target states with non-trivial (and thus interesting) properties.

Since an isolated quantum system fundamentally follows pure Hamiltonian dynamics, asymptotic stabilization necessarily requires interaction with the external world and relies on the theory of open quantum systems. Such interactions can involve measurement and feedback action, called measurement-based feedback, or also control by tailored interaction as broadly advocated in [START_REF] Willems | Control as interconnection[END_REF] ⋆ This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The authors were partially supported by the ANR, Projet Blanc EMAQS ANR-2011-BS01-017-01 and Projet C-QUID BLAN-3-139579.

and called coherent feedback in the quantum context. Measurement-based feedback introduces specific difficulties because quantum measurement is fundamentally limited to partial state knowledge and always perturbs the measured system ("back-action"). Controller design therefore always needs to follow an interactions-based reasoning (see e.g. [START_REF] Dotsenko | Quantum feedback by discrete quantum non-demolition measurements: towards on-demand generation of photon-number states[END_REF], [START_REF] Sayrin | Real-time quantum feedback prepares and stabilizes photon number states[END_REF]). Coherent feedback involves a specific structure, based on joint evolution on a tensor product of the interacting subsystems that leads to dissipative and/or stochastic quantum dynamics for the target subsystem (see e.g. [START_REF] James | Quantum dissipative systems and feedback control design by interconnection[END_REF], [START_REF] Kerckhoff | Designing quantum memories with embedded control: photonic circuits for autonomous quantum error correction[END_REF].

Reservoir engineering is a systematic method related to coherent feedback for open loop stabilization of quantum systems through tailored interaction. For discrete-time quantum systems, the target system repeats the same interaction with a succession of auxiliary systems, which are discarded after interaction. The dynamics on the target system resulting from repeating the same interaction process, takes the form of a Kraus map, see [START_REF] Kraus | States, effects and operations: fundamental notions of quantum theory[END_REF]. A random Kraus map would generally drive the system to a mixed quantum state (featuring classical uncertainties). For reservoir action, interaction with each individual auxiliary system must be tailored such that the Kraus map has a desired pure state as asymptotically stable equilibrium. General techniques have been proposed to tailor Kraus maps, provided any chosen unitary evolutions can be applied to the target subsystem by controlling its Hamiltonian (kind of 'complete actuation' on the sub-system Hamiltonian, see e.g. [START_REF] Ticozzi | Analysis and synthesis of attractive quantum Markovian dynamics[END_REF], [START_REF] Bolognani | Engineering stable discretetime quantum dynamics via a canonical QR decomposition[END_REF]). There are however many systems where control over the Hamiltonian is instead very restricted.

This paper considers such a situation, where the target system is an electromagnetic field mode, interacting with three-level atoms as auxiliary systems. This quantum electrodynamics situation is a prototype for so-called universal spring-spin systems (see e.g. [START_REF] Haroche | Exploring the quantum: atoms, cavities and photons[END_REF]). The spin-spring Hamiltonian is controlled by shifting the frequencies of the atomic transitions as a function of time, through the Stark effect. This yields a very low-dimensional input signal to tailor the target system's evolution governed by the resulting Kraus map. [START_REF] Sarlette | Stabilization of nonclassical states of the radiation field in a cavity by reservoir engineering[END_REF] propose a method to stabilize socalled 'Schrödinger cat states' with this setup. It builds the overall unitary interaction operator as a symmetric product of non-commuting basic operators, by varying the input signal during the field's interaction with each atom. We prove here that stabilizing pure photon states ('Fock states') is also possible. [START_REF] Rempe | Observation of sub-Poissonian photon statistics in a micromaser[END_REF] have proposed a method based on 'trapping state conditions', where the auxiliary systems are two-level atoms interacting resonantly with the quantized field mode: the target Fock state is an equilibrium of the Kraus map but it is a saddle point with stable manifold in some but not all relevant directions. The present paper proposes a modification of this method that makes the target Fock state a stable equilibrium of the Kraus map in the most relevant Hilbert subspace. We therefore build an interaction that combines the 'trapping state' approach of [START_REF] Rempe | Observation of sub-Poissonian photon statistics in a micromaser[END_REF] with the construction of symmetric products of non-commuting operators from [START_REF] Sarlette | Stabilization of nonclassical states of the radiation field in a cavity by reservoir engineering[END_REF].

We give formal convergence properties for the resulting scheme, both in absence and in presence of a disturbing environment (Theorem 1 based on the construction of a strict Lyapunov function, and Proposition 2). In section 2 we define the target system, the auxiliary three-level atoms, the interaction Hamiltonian with its scalar control input u and the associated Kraus map. In section 3, the operators appearing in the Kraus map are computed for our open-loop piecewise constant control (10). Section 4 is devoted to convergence analysis. Simulations in Section 5 briefly explore the influence of parameter uncertainties and illustrate the robustness for realistic QED parameters.

SYSTEM DESCRIPTION

We consider a quantum electrodynamics setup as described e.g. in [START_REF] Haroche | Exploring the quantum: atoms, cavities and photons[END_REF]. The target system is a field mode, with infinite-dimensional Hilbert space H = span(|0 , . . . , |n , ... ) and free Hamiltonian

H f = +∞ n=0 n ω f |n n| (1)
where ω f > 0 is the field mode pulsation and the index n gives the photon number. This paper denotes by |n the pure photon number eigenstates, called Fock states. The photon number operator is defined by N = +∞ n=0 n |n n| = H f / ω f . We will further use the notation

f N = f (N) = +∞ n=0 f (n) |n n| = +∞ n=0 f n |n n|
for an operator that is diagonal in the Fock basis, for any function1 f : N → C. We denote by H n2 n1 the Hilbert subspace spanned by Fock states |n 1 , |n 1 + 1 , ..., |n 2 . A stream of identical atoms consecutively interact with this field mode according to the Jaynes-Cummings model, playing the role of a 'reservoir' to stabilize the field in a target state. We consider three atomic levels |g , |e , |m , with free Hamiltonian H a = ω m |m m| -ω g |g g| (2) up to an irrelevant term that is a multiple of the identity operator. The transition frequencies between levels (|g , |e ) and (|e , |m ), that is ω g ∈ R and ω m ∈ R respectively, depend on an input u ∈ R. The latter represents an energy shift induced on |e by an external field through a Stark effect, such that ω g (u) = ω g + u and ω m (u) = ω m -u .

(3) The constants ω g and ω m are the transition pulsations in absence of external field. For simplicity, the following assumes that ω g (u) > 0 and ω m (u) > 0: |g corresponds to the lowest atomic level whereas |e and |m are the first and second excited states (3-level ladder system). The proposed method can be adapted to other energy arrangements, like V-structures, by adding short external control pulses that switch the atomic state at specific points in our scheme.

To make atomic transitions and field mode interact, we consider the following realistic situation, in the spirit of [START_REF] Santos | Observing different quantum trajectories in cavity QED[END_REF]:

|ω g -ω f |, |ω m -ω f | ≪ ω f ; |u| ∼ |ω g -ω f |, |u| ∼ |ω m -ω f |.
Then with the standard rotating wave approximation, the atom-field interaction is described by the Hamiltonian:

H c = i Ω 2 ( a † (|g e| + |e m|) -a (|e g| + |m e|) ) . (4)
Here i = √ -1 and Ω is the interaction strength factor, assumed to be equal for transitions (g, e) and (e, m); photon annihilation operator a is defined by a = +∞ n=1

√

n |n-1 n| in the Fock basis; and † denotes the adjoint of an operator (complex conjugate transpose of the associated matrix). We have the fundamental identities a † a = N, as well as a f (N) = f (N + I) a and its adjoint f (N) a † = a † f (N + I) for any function f : N → C. Equation (4) essentially expresses that atomic state can raise from |g to |e or from |e to |m by absorbing one photon from the field, or fall inversely by releasing one photon. The propagator U, expressing the transformation that the joint atom-field state undergoes during interaction, follows the Schrödinger equation

d dt U(t) = -i ( H f + H a + H c ) U(t)
(5) with initial condition U(t 0 ) = I the identity operator. A standard change of variables |ψ → e iH f t |ψ on field state and (|g , |e , |m ) → (e -iω f |g , |e , e iω f |m ) on atomic states leads to 'interaction coordinates'. In these coordinates the propagator follows

d dt U(t) = -i H JC U(t) (6)
where the Jaynes-Cummings Hamiltonian writes The atoms are sent one after the other, every T s seconds, to undergo the same interaction with the field. We denote the field mode density operator just before interacting with the (k + 1)th atom by ρ k . The initial state |u at ∈ C 3 of the atoms can be chosen, as well as the Stark detuning signal u(t) during interaction time [0, T ], with T ≤ T s . Denote U T the solution at time T of (6) with U(0) = I and with the chosen u(t), governing a time-varying H JC in (7). Then the atom-field joint state just after the k + 1th interaction is given by U T (ρ k ⊗ |u at u at |) U T . This generally corresponds to an entangled situation. Since we do not measure the final atomic state, the expected field evolution follows the Kraus map

H JC (u) = (∆ m -u) |m m| -(∆ g + u) |g g| + H c (7) with ∆ m = ω m -ω f and ∆ g = ω g -ω f .
ρ k+1 = Φ(ρ k ) = M g ρ k M † g + M e ρ k M † e + M m ρ k M † m , (8)
ρ k → ρ ∞ = |ψ ∞ ψ ∞ |.

CONTROL DESIGN

Our objective is to stabilize a given Fock state |ψ ∞ = |n . [START_REF] Rempe | Observation of sub-Poissonian photon statistics in a micromaser[END_REF] have noted that in absence of the |m level (i.e. |∆ m -u| ≫ Ω), a single atomic transition (|g , |e ) in perfect resonant interaction with the field (i.e. ∆ g + u = 0) allows to "trap" states below |n . The corresponding propagator (obtained by direct integration of (6) which is then 2×2 block-diagonal) writes

U r = cos( θr √ N 2 ) |g g| + cos( θr √ N+I 2 ) |e e| (9) -a sin( θr √ N 2 ) √ N |e g| + sin( θr √ N 2 ) √ N a † |g e| ,
where θ r = t r Ω is the interaction strength integrated over chosen interaction time t r . Then taking θ r = 2π/ √ n + 1, the operator in (9) implies no exchange between joint state components |g ⊗ |n + 1 and |e ⊗ |n . The subspace H n 0 spanned by Fock states |0 , |1 , ...|n then remains decoupled from the rest of the field Hilbert space throughout reservoir action. Now take |u at = |e , thus

M g = sin( θr √ N 2 ) √ N a † , M e = cos( θr √ N+I 2
) and M m = 0. Then ρ k following (8) starting from ρ 0 with support in H n 0 converges to the trapping state |n n| [Haroche and Raimond 2006, page 210]. But if the support of ρ 0 is in H 4n+3 n+1 , then ρ k converges to |4n + 3 4n + 3| as the field gets continuously excited. Therefore any fraction of density that is pushed above |n is lost away to high photon numbers. Since perturbations will always induce transitions between nearby energy states, this makes the method of [START_REF] Rempe | Observation of sub-Poissonian photon statistics in a micromaser[END_REF] unusable in practice as it leaves equilibrium |n unstable in important directions.

A robust stabilization method should enlarge the basin of attraction of |n n| to include at least any ρ 0 with support in H n2 n1 for some n 1 < n < n 2 . We achieve such stabilization with n 1 = 0 and n 2 = 4n + 3 (see Theorem 1) by exploiting the possibility of varying u(.) during the interaction. Specifically, we take

u(t) =    -∆ g for t ∈ [0, (T -t s )/2] ∆ m for t ∈ [(T -t s )/2, (T + t s )/2] -∆ g for t ∈ [(T + t s )/2, T ] . (10)
Fast set-point changes can indeed suitably be experimentally implemented. The switching time t s and overall interaction time T will be tuned to optimize operation. We still take |u at = |e as initial atomic state.

The propagator U T , solution of ( 5) with u given by ( 10), readily writes

U T = U 1 U 2 U 1 where U 1 = exp[-iH JC (-∆ g ) (T -t s )/2] is the solution at t = (T - t s )/2 of (5) starting at t 0 = 0, with constant u = -∆ g ; and U 2 = exp[-iH JC (∆ m ) t s ]
is the solution at t = t s of (5) starting at t 0 = 0, with constant u = ∆ m . We compute those operators using quantum Hamiltonian perturbation theory on the decoupled subspaces spanned by (|g ⊗ |n + 1 , |e ⊗ |n , |m ⊗ |n -1 ) and neglecting terms of order Ω/∆ ≪ 1. Up to this approximation, the states |m ⊗|n-1 (resp. |g ⊗ |n + 1 ) remain decoupled from the rest for U 1 (resp. U 2 ). One gets:

U T |e = Mg a † e i∆ts + cos θ2 √ N 2 sin(θ 1 √ N + I) 2 √ N + I |g + Me cos 2 θ1 √ N+I 2 cos θ2 √ N 2 -e i∆ts sin 2 θ1 √ N+I 2 |e - Mm e -i∆(T -ts)/2 a sin θ2 √ N 2 √ N cos θ1 √ N+I 2 |m (11)
with θ 1 = Ω (T -t s )/2 and θ 2 = Ω t s . To make the target field state |n invariant under the Kraus map (8), we make it invariant under U T |e . This is achieved with the trapping-like condition:

(T -t s ) = 2π Ω √ n + 1 ⇔ θ 1 = π √ n + 1 . ( 12
)
For simplicity, we take ∆ t s = 0 nominally2 . The value of ∆(T -t s ) is irrelevant as it drops out of the Kraus map for the field evolution. The value of θ 2 remains to be fixed.

CONVERGENCE ANALYSIS

Condition (12) makes the subspace H (4n+3) 0

invariant by M g , M e and M m . We denote P (4n+3) 0 the orthogonal projection onto H (4n+3) 0

. Consider a candidate Lyapunov function of the form V (ρ) = trace(f N ρ), for some function f (n) to be determined. Then ( 8) and ( 11) lead to

V (Φ(ρ)) -V (ρ) = trace ρ cos 2 ( αN 2 ) sin 2 (β N ) ( f (N -I) -f (N) ) + trace ρ sin 2 (α N ) cos 4 ( βN 2 ) ( f (N + I) -f (N) )
with α N = π N+I n+1 and β N = θ 2 √ N/2. Note that the last line of the above equation vanishes for ρ = |4n + 3 4n + 3| and any function f N , reflecting the decoupling of H (4n+3) 0 from the remainder of the Hilbert space. To formally restrict ourselves to H (4n+3) 0

, we can take f (n) = f (4n+3) for all n > 4n+3, such that f (N-I)-f (N) and f (N+I)f (N) vanish on H +∞ (4n+4) . Further take η ∈ (0, 1),

f (n) = 0, f (n + 1) = f (n -1) = 1 and set f (n-1) = f (n) + η sin 2 αn 2 cos 2 βn 2 (f (n) -f (n+1)) for 0 < n < n , f (n+1) = f (n) + η sin 2 βn 2 (f (n) -f (n-1)) (13)
for n < n < 4n + 3 . Then V (Φ(ρ))-V (ρ) = trace(q N ρ) with q n = 0 for n = n, n > 4n + 3, and

q n = sin 2 α n cos 4 βn 2 (η sin 2 βn 2 -1) (f (n)-f (n+1)) for 0 ≤ n < n , (14)
q n = sin 2 β n cos 2 αn 2 (η sin 2 αn 2 cos 2 βn 2 -1) (f (n)-f (n-1)) for n < n ≤ 4n + 3 . We then have the following convergence result.

Theorem 1. Consider the dynamics (8) where M g , M e and M m are defined by ( 11) with ( 12), and its restriction to density operators ρ with support in 13) is a strict Lyapunov function: for any ρ 0 with support in H (4n+3) 0 , ρ k converges towards the fixed point ρ ∞ = |n n|.

H (4n+3) 0 . Assume that θ 2 = kπ/ √ n for all (n, k) ∈ {1, ..., 4n + 3} × N. Then V (ρ) built with (
Proof: Thanks to the assumption on θ 2 , (13) implies f (n) > f (n -1) for n < n ≤ 4n + 3 and f (n) > f (n + 1) for 0 < n < n. Then the same assumption ensures that q n is strictly negative for all n ≤ 4n+3 except n = n. Writing ρ = j p j |ψ j ψ j | (spectral decomposition with p j > 0,

j p j = 1) then yields V (Φ(ρ)) -V (ρ) = j p j ψ j | q N |ψ j < 0 unless P (4n+3) 0 |ψ j = s j |n with s j ∈ C for all j, implying P (4n+3) 0 ρP (4n+3) 0 = p|n n| for some p ∈ R. Thus V is a strict Lyapunov function in H (4n+3) 0
as stated.

Remark:

The above construction of f (n) can in fact be extended to n < 9n + 8. For generic θ 2 , such that sin(2β n ) never vanishes, the resulting V is then a non-strict Lyapunov function on the invariant Hilbert subspace H (9n+8) 0 , with the Lasalle invariance principle ensuring convergence of ρ to a ρ ∞ supported on the subspace spanned by |m , |9m + 8 . Considering even larger Hilbert spaces, one shows that ρ converges to a state with nonzero population only on Fock states |(2l + 1) 2 (n + 1) -1 for l integer. The experiments working in very low temperature environments ensure that decoherence usually pulls the field state towards vacuum (Fock state |0 ) and depopulates high-number Fock states.

Tailored interaction (10) with the atomic stream thus makes the otherwise isolated field converge to |n for virtually all θ 2 > 0. This confirms the interest of this symmetric product operator approach. We next analyze how the latter can be optimized to strengthen convergence w.r.t. external disturbances. We therefore add to the evolution model a typical relaxation disturbance, also called decoherence: evolution between consecutive atomic samples becomes

ρ k+1 = Φ(ρ k ) -Γ - 2 [NΦ(ρ k ) + Φ(ρ k )N -2aΦ(ρ k )a † ] (15) -Γ + 2 [(N + I)Φ(ρ k ) + Φ(ρ k )(N + I) -2a † Φ(ρ k )a] with Γ + = κn th T s ≪ Γ -= κ(1+n th )T s ≪ 1.
The terms in Γ -and Γ + model interaction with a thermal environment that induces photon annihilation and creation respectively. Parameter κ models coupling strength to this environment, while n th is the average number of thermal photons per mode in the environment. The invariant-subspace structure no longer rigorously holds, but we can invoke a physical argument to still truncate our computations at n ≤ 9n + 8, ensuring that the discretized model remains valid and all parameters in the following are well-behaved.

Writing the operator ρ k as a matrix with components [ρ k ] a,b , for a ≥ 0 and b ≥ 0, the evolution (15) couples component [ρ k ] a,b only to components [ρ k ] a+l,b+l i.e. on the same diagonal of the matrix. To analyze how the fidelity n|ρ k |n to target |n n| evolves, we may thus reduce our investigation to the vector

r k containing the principal diagonal of ρ k , that is [r k ] a = [ρ k ] a,a for a = 0, 1, 2, ... . Evolution (15) yields r k+1 = B • A • r k
with A and B tridiagonal real positive non-symmetric matrices, representing reservoir and decoherence respectively. The upper, lower and principal diagonals of B (respectively

A) have elements b n = Γ -n (resp. d n = sin 2 β n cos 2 αn 2 ) for n ∈ {1, 2, ...}; c n = Γ + n (resp. e n = sin 2 α n cos 4 βn 2 ) for n ∈ {0, 1, 2, ...}; and 1 -c n -b n (resp. 1 -d n -e n ).
A and B are thus column-stochastic, reflecting conservation of trace(ρ) = 1 T r where 1 is the vector of all ones. Therefore B • A has at least one eigenvalue 1. The corresponding 1-eigenvector r * characterizes photon populations for a field pointer state under reservoir and decoherence.

We try to approximate it by viewing B • A as a small perturbation of A. Denote x 0 the r-vector corresponding to |n n|, let

R 0 = A-I and R 1 = (B -I)(A-I)+ (B -I).
Then we know that R 0 x 0 = 0 with 1 T x 0 = 1, i.e. x 0 is the steady-state solution r * when B = I (no perturbation). In presence of a thermal environment, we get r * = x 0 + x 1 solution of (R 0 + R 1 )(x 0 + x 1 ) = 0, 1 T x 1 = 0 . (16)

Proposition 2. Approximating R 1 x 1 ≈ 0, problem ( 16) can be explicitly solved. It gives 1+x 1 n as estimated fidelity of ρ ∞ to our goal, where

-x 1 n = b n e n-1 n m=1 m l=2 d n-l+1 e n-l + c n d n+1 m>0 m l=2 e n+l-1 d n+l .
An approximation error of order (x 1 n)

2 is expected.

Proof: Solving ( 16) approximated (note that d n = e n = 0) fixes the components of x 1 , except x 1 n which remains free:

x 1 n-1 = b n/e n-1 ; x 1 n = d n+1 e n x 1 n+1 ∀ n < n -1 ; x 1 n+1 = c n/d n+1 ; x 1 n = e n-1 d n x 1 n-1 ∀ n > n + 1 .
Then ( 16) determines x 1 n < 0. Proposition 2 can be used to optimize θ 2 for maximal fidelity in presence of decoherence, see next Section. Note that θ 2 = 0 (the case of [START_REF] Rempe | Observation of sub-Poissonian photon statistics in a micromaser[END_REF]) would yield d n = 0 for all n. The small-x 1 approximation would then lead to an invalid recurrence, suggesting that decoherence leads to large x 1 i.e. the method of [START_REF] Rempe | Observation of sub-Poissonian photon statistics in a micromaser[END_REF] is poorly robust.

SIMULATIONS

For the simulations we consider realistic parameters corresponding to the cavity quantum electrodynamics setup at Ecole Normale Supérieure, Paris. See e.g. [START_REF] Haroche | Exploring the quantum: atoms, cavities and photons[END_REF], [START_REF] Deléglise | Reconstruction of non-classical cavity field states with snapshots of their decoherence[END_REF] for detailed explanations. Vacuum Rabi frequency is given by Ω/2π = 50 kHz and we take ∆ ≈ 100Ω. We numerically compute propagators for the exact interaction (7) and u given by (10). For each simulation we slightly adapt ∆ to optimize fidelity, see footnote 2. Evolution of ρ k is computed starting from a vacuum initial state ρ 0 = |0 0|. Figure 1 illustrates the good working principle of the method, despite our approximate reasoning: ρ k+1 = Φ(ρ k ) converges essentially exactly to ρ ∞ = |n n| for all n ∈ {1, 2, ..., 8}. The simulations are run with an arbitrary θ 2 = 1/ √ n.

We next add decoherence. We take 1/κ = 0.1 s and cryogenic n th = 0.05, corresponding to current high-standard experiments. This environment-induced decoherence is in competition with our reservoir strength, that is mainly the time between consecutive atoms. The latter can realistically3 be set to T s = 60 µs, but there is only a 0.3 probability that an interacting atom is indeed present when trying to send one. The expected evolution from ρ k to ρ k+1 is thus similar to (a less approximated version of) (15) except that operator 0.7 I + 0.3 Φ replaces Φ. Figure 2 represents the evolution of the diagonal elements of ρ with the reservoir of [START_REF] Rempe | Observation of sub-Poissonian photon statistics in a micromaser[END_REF] (top) and with our symmetric-interaction reservoir (bottom), for a target n = 3. For the latter, after the |3 state has built up, it progressively drives away towards |15 = |4n + 3 and further to higher photon numbers (here accumulating where our Hilbert space is truncated). In contrast our scheme clearly stabilizes a state close to |3 . Achievable steady-state fidelities are represented on Fig. 3. We also show the values estimated from Proposition 2. They agree with simulations within the expected approximation error, confirming our theoretical analysis. The selected optimal values of θ 2 seem to satisfy θ 2 √ n ≈ 3π/4.

Finally, we consider errors in model parameters as another important robustness criterion. Small variations in θ 2 appear to give no detectable effect, indicating a rather flat optimum in θ 2 . Absolute errors of ±π/8 on ∆t s also barely affect fidelity (less than 1%). The fidelities obtained with our reservoir subject to errors in θ 1 (and still in presence of decoherence) are represented for each n by the 3rd and 4th bars from left on Fig. 3. Relative errors of ±2% have a detectable but tolerable effect; especially, setting θ 1 in an interval centered slightly below the ideal value seems to be a good robustness compromise. The same ±2% error on θ 1 would be drastically detrimental with the scheme of [START_REF] Rempe | Observation of sub-Poissonian photon statistics in a micromaser[END_REF]: even in absence of a disturbing environment (Γ -= Γ + = 0) the fidelity to |n would then quickly decrease towards zero, dropping to about 0.15 already after 0.1 s and below 0.01 after 0.25 s. Overall our construction of atom-field interaction as a product of noncommuting transformations thus leads to a significantly more robust stabilization scheme.

CONCLUSION

This paper proposes an 'engineered reservoir' to stabilize Fock states of a quantum harmonic oscillator thanks to its interaction with a stream of three-level systems. We use a single control signal to tailor a time-varying Hamiltonian interaction. We prove that the resulting propagator yields a Kraus map that robustly 'traps' the spring state on a desired Fock state. This seems to be a potentially practical open-loop alternative to measurement-based feedback for achieving high-fidelity stabilization of Fock states. The proposed method admits several variations for experimental implementation. Among others, a similar stabilizing effect is obtained by using a stream of two-level atoms each undergoing one of two different interactions. Given the practical possibilities shown in the present and previous et al. [1990]. The third and fourth bars from left correspond to the same conditions as the first ones, but incorporating a systematic error of -2% and +2% respectively on θ 1 .

papers, future work could further investigate systematic methods for designing products of interactions that robustly stabilize quantum states.

  where the operators M g , M e , M m acting only on the field mode are identified from U T and |u at : ∀|ψ ∈ H, U T |ψ |u at = M g |ψ |g + M e |ψ |e + M m |ψ |m . The goal of open-loop stabilization by reservoir engineering is to select u(t) and |u at such that the dynamics (8) asymptotically stabilize a target pure state

Fig. 1 .

 1 Fig. 1. Fidelity n|ρ k |n of ρ k to target state |n as a function of atomic interaction k, for n = 1, 2, ..., 8 (going from top to bottom curve) and Γ -= Γ + = 0 i.e. no environmental disturbance.

Fig. 2 .

 2 photon number

Fig. 3 .

 3 photon number

  The goal being to allow separate interactions of the two atomic transitions with the field, we assume that the |m and |g levels are attributed sufficiently different frequencies in H JC , i.e. |∆ g + ∆ m | =: ∆ ≫ Ω. Note that H JC acts in parallel on a set of decoupled subspaces spanned by (|g ⊗ |n + 1 , |e ⊗ |n , |m ⊗ |n -1 ). The associated matrix operators are thus block-diagonal with blocks of size 3×3 at most, which facilitates analysis.

We take the convention, especially useful in quantum mechanics, that N includes 0.

To this end, the value of ∆ can be slightly tuned by adjusting the trap that governs field mode frequency ω f . Indeed since ∆ ≫ Ω, a small shift in ∆ allows to sensibly tune ∆ ts for all ts that yield non-negligible values of θ 2 = Ωts.

Although the required values of θ 1 and θ 2 allow smaller T , we are experimentally limited to periods of the order of Ts.

ACKNOWLEDGEMENTS

The authors thank Michel Brune, Igor Dotsenko and Jean-Michel Raimond from Ecole Normale Supérieure for useful discussions.


Christophe Crespelle
email: christophe.crespelle@inria.fr

Philippe Gambette
email: philippe.gambette@univ-mlv.fr

Linear-time Constant-ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs

In this paper we consider a graph parameter called contiguity which aims at encoding a graph by a linear ordering of its vertices. We prove that the contiguity of cographs is unbounded but is always dominated by O(log n), where n is the number of vertices of the graph. And we prove that this bound is tight in the sense that there exists a family of cographs on n vertices whose contiguity is Ω(log n). In addition to these results on the worst-case contiguity of cographs, we design a linear-time constant-ratio approximation algorithm for computing the contiguity of an arbitrary cograph, which constitutes our main result. As a by-product of our proofs, we obtain a min-max theorem, which is worth of interest in itself, stating equality between the rank of a tree and the minimum height its path partitions.

Introduction

In many contexts, such as genomics, biology, physics, linguistics, computer science and transportation for examples, industrials and academics are led to algorithmically treat large dataset organised in the form of networks or graphs. The algorithms used to do so generally make extensive use of neighborhood queries, which, given a vertex x of a graph G, ask for the list of neighbors of x in G. Therefore, as pointed out by [START_REF] Turan | On the succinct representation of graphs[END_REF], due to the huge size of the graphs considered, finding compact representations of a graph providing optimal-time neighborhood queries is a crucial issue in practice.

One possible way to achieve this goal is to find an order σ on the vertices of G such that the neighborhood of each vertex x of G is an interval in σ. In this way, one can store the list of vertices of the graph in the order defined by σ and assign two pointers to each vertex: one toward its first neighbor in σ and one toward its last neighbor in σ. Therefore, one can answer adjacency queries on vertex x simply by listing the vertices appearing in σ between its first and last pointer. It must be clear that such an order on the vertices of G does not exist for all graphs G. Nevertheless, this idea turns out to be quite efficient in practice and some compression techniques are precisely based on it [START_REF] Boldi | The webgraph framework I: compression techniques[END_REF][START_REF] Boldi | Codes for the world wide web[END_REF]: they try to find orders of the vertices that group the neighborhoods together, as much as possible.

When one relaxes the constraints of the initial problem by rather asking for the minimum k such that there exists an order σ on the vertices of G where the neighborhood of each vertex is split in at most k intervals, this gives rise to a graph parameter called the contiguity of G [START_REF] Crespelle | Efficient neighbourhood encoding for interval graphs and permutation graphs and O(n) breadth-first search[END_REF]. This parameter was originally introduced in the broader context of binary matrices under the name k-consecutiveones property [START_REF] Goldberg | Four strikes against physical mapping of DNA[END_REF]. It is worth to note that there are two variants of the parameter, respectively called open contiguity and closed contiguity, depending on whether one considers open neighborhoods (excluding the vertex itself) or closed neighborhoods (always containing the considered vertex). But this distinction is not fundamental as the two parameters always differ by at most one.

Here, we are interested in determining what is the worst-case contiguity for the cographs on n vertices, which are the graphs having no induced P 4 (path on 4 vertices). We also design an approximation algorithm that computes the contiguity of any cograph up to a constant ratio, in linear time with regard to the size of the input.

Related works. Only very little is known about the contiguity of graphs. Only the class of graphs having open contiguity 1 and the class of graphs having closed contiguity 1 have been characterized: the former are biconvex graphs [START_REF] Brandstädt | Graph Classes: a Survey[END_REF] and the latter are proper interval graphs [START_REF] Roberts | Representations of indifference relations[END_REF]. But the classes of graphs having contiguity at most k, where k is an integer greater than 1, have not been characterized, even for k = 2. Actually, closed contiguity has initially been studied in the context of 0 -1 matrices and [START_REF] Goldberg | Four strikes against physical mapping of DNA[END_REF][START_REF] Johnson | Compressing large boolean matrices using reordering techniques[END_REF][START_REF] Wang | Hamiltonicity of regular graphs and blocks of consecutive ones in symmetric matrices[END_REF] showed that deciding whether an arbitrary graph has closed contiguity at most k is NPcomplete for any fixed k ≥ 2. For arbitrary graphs again, [START_REF] Gavoille | The compactness of interval routing[END_REF] (Corollary 3.4) gave an upper bound on the value of closed contiguity which is n/4 + O( √ n log n), whose interest lies in the constant 1/4 since it is clear that the contiguity of a graph is always less than n/2 (where n is the number of vertices of the graph). Finally, let us mention that [START_REF] Crespelle | Efficient neighbourhood encoding for interval graphs and permutation graphs and O(n) breadth-first search[END_REF] showed that the contiguity is unbounded for interval graphs as well as for permutation graphs, and that it can be up to Ω(log n/ log log n).

Our results. In this paper, we show that even for cographs, the contiguity is unbounded, but is dominated by O(log n) for a cograph on n vertices. To this purpose, we show (in Section 4) that the contiguity of a cograph G is mathematically equivalent the maximum height of a complete binary tree included (as a minor) in the cotree of G. This also allows us to exhibit a family of cographs (G n ) n∈N on n vertices whose asymptotic contiguity is Ω(log n), which implies that our O(log n) bound is tight. Furthermore, from this result, we derive in Section 5 a constant-ratio approximation algorithm that computes the contiguity of an arbitrary cograph (up to a multiplicative constant) in linear time wrt. the size of the input, that is O(n) time provided that the input cograph is given by its cotree (see Section 1 for a definition). In addition, our algorithm can also provide a linear ordering σ of the vertices of G, together with the pointers from each vertex to the at most k intervals partitioning its neighborhood, that realizes a k which is in a constant ratio from the optimal one, i.e. the contiguity of G. In this case, the complexity of our algorithm is linear wrt. the size of the output, that is O(kn) time.

As a by-product of our proofs, we also establish in Section 2 a min-max theorem which is worth of interest in itself: the maximum height of a complete binary tree included (as a minor) in a tree T (known as the rank of tree T [START_REF] Ehrenfeucht | Learning decision trees from random examples[END_REF][START_REF] Gavaldà | Algebraic characterizations of small classes of boolean functions[END_REF]) is equal to the minimum height of a partition of T into vertex-disjoint paths.

Preliminaries.

All graphs considered here are finite, undirected, simple and loopless. In the following, G denotes a graph, V (or V (G) to avoid ambiguity) denotes its vertex set and E (or E(G)) its edge set. We use the notation G = (V, E) and we denote |V | = n. The set of subsets of V is denoted by 2 V . An edge between vertices x and y will be arbitrarily denoted by xy or yx. The (open) neighborhood of x is denoted by N (x) (or N G (x) to avoid ambiguity) and its closed neighborhood by

N [x] = N (x)∪{x}. The subgraph of G induced by the subset of vertices X ⊆ V is denoted by G[X] = (X, {xy ∈ E | x, y ∈ X}).
Cographs are the graphs that do not have any P 4 (path on 4 vertices) as induced subgraph. They are also known to be the graphs G admitting a cotree, i.e. a rooted tree T whose leaves are the vertices of G, and whose internal nodes are labelled series or parallel with the following property: any two vertices x and y of G are adjacent iff the least common ancestor u of leaves x and y in T is a series node. Otherwise, if u is a parallel node, x and y are not adjacent.

For a rooted tree T and a node u ∈ T , the depth of u in T is the number of edges in the path from the root to u (the root has depth 0). The height of T , denoted by height(T ) or simply h(T ), is the greatest depth of its leaves. For a rooted tree T , the subtree of T rooted at u, denoted by T u , is the tree induced by node u and all its descendants in T . In the following, the notion of minors of rooted trees is central. This is a special case of minors of graphs (see e.g. [START_REF] Lováz | Graph minor theory[END_REF]), for which we give a simplified definition in the context of rooted trees.

Definition 1.1. The contraction of edge uv in a rooted tree T , where u is the parent of v, consists in removing v from T and assigning its children (if any) to node u. A rooted tree T is a minor of a rooted tree T if it can be obtained from T by a sequence of edge contractions.

Let us now formally define the contiguity of a graph.

Definition 1.2. A closed p-interval-model (resp. open p-interval-model) of a graph G = (V, E) is a linear order σ on V such that ∀v ∈ V, ∃(I 1 , . . . , I p ) ∈ (2 V ) p such that ∀i ∈ 1, p , I i is an interval of σ and N [v] = 1≤i≤p I i (resp. N (v) = 1≤i≤p I i ).
The closed contiguity (resp. open contiguity) of G, denoted by cc(G) (resp. oc(G)) , is the minimum integer p such that there exists a closed p-interval-model (resp. open p-interval-model) of G.

It is worth to note that the closed and open contiguity never differ by more than one. Indeed, given a closed k-interval model of a graph G, we directly get an open k + 1-interval model for G by simply splitting, for each vertex x, the interval containing x into (at most) two intervals. Conversely, adding (at most) one trivial interval {x} for each vertex x in an open k-interval-model results in a closed (k +1)-interval model. Therefore, in all the rest of the paper, we only consider closed contiguity, but all our results also hold for open contiguity. In the following, we abusively extend the notion of contiguity to cotrees referring to the contiguity of their associated cograph.

Some general results on the rank of trees

In this section, we give two general results on trees which will play a key role in the rest of the paper. The first result links the rank of a tree T with the minimum height of a partition of vertices of T into paths.

The rank [START_REF] Ehrenfeucht | Learning decision trees from random examples[END_REF][START_REF] Gavaldà | Algebraic characterizations of small classes of boolean functions[END_REF] of a tree T is the maximal height of a complete binary tree obtained from T by edge contractions, that is: rank(T ) = max{h(T ) | T complete binary tree, minor of T }. A path partition of a tree T is a partition {P 1 , . . . , P k } of V (T ) such that for any i, the subgraph T [P i ] of T induced by P i is a path, as shown in Figure 1(a). The partition tree of a path partition P, denoted by T p (P), is the tree whose nodes are P i 's and where the node of T p (P) corresponding to P i is the parent of the node corresponding to P j iff some node of P i is the parent in T of the root of P j (see Fig. 1(b)). The height of a path partition P of a tree T , denoted by h(P), is the height h(T p (P)) of its partition tree. The path-height of T is the minimal height of a path partition of T , that is ph(T ) = min{h(P) | P path partition of T }. Theorem 2.1. For any rooted tree T , rank(T ) = ph(T ).

Sketch of proof. It is not difficult to show that the path-height of a tree T is at least the path-height of any tree T included in T as a minor. On the other hand, a simple recursion on the height of a complete binary tree shows that its path-height is at least its height. It follows that the path-height of any tree T is at least the maximum height of a complete binary tree T included as a minor in T , that is ph(T ) ≥ rank(T ). The converse inequality, namely ph(T ) ≤ rank(T ), can be shown by induction on rank(T ). Indeed, consider a tree T such that rank(T ) = k + 1. The nodes u of T such that rank(T u ) = k + 1 form a path P containing the root of T . By definition, any node v ∈ P is such that rank(T v ) ≤ k. Then, by the induction hypothesis,

ph(T v ) ≤ rank(T v ) ≤ k. And it follows that ph(T ) ≤ max v ∈P ph(T v ) + 1 ≤ k + 1 = rank(T ). A detailed version of this proof is given in Appendix A, in Theorem 5.1. 2
We now consider bicolored trees, i.e. trees whose nodes are colored either black or white. We define the black rank (resp. white rank ), denoted r B (T ) (resp. r W (t)), of a bicolored tree T as the maximum height of an entirely black (resp. entirely white) complete binary tree being a minor of T . Theorem 2.2. For any bicolored complete binary tree T , r B (T ) + r W (T ) ≥ h(T ) -1.

Sketch of proof.

The proof is by induction on h(T ). Consider a complete binary bicolored tree T of height k + 1, whose root is colored black wlog. and has two children denoted by u 1 and u

2 . If r B (T u 1 ) = r B (T u 2 ), then r B (T ) = r B (T u 1 ) + 1. And since r W (T ) ≥ r W (T u 1 ), by the induction hypoth- esis, we obtain r B (T ) + r W (T ) ≥ h(T u 1 ) + 1 -1 = h(T ) -1. On the other hand, if r B (T u 1 ) = r B (T u 2 ), then assume wlog. that r B (T u 1 ) > r B (T u 2 ). Then, we have r B (T ) + r W (T ) ≥ r B (T u 1 ) + r W (T u 2 ) ≥ r B (T u 2 ) + 1 + r W (T u 2 )
, and by the induction hypothesis, we obtain the desired inequality for T . A detailed version of this proof is given in Appendix A, in Theorem 5.2. 2

An upper bound for the contiguity of cographs

We now prove that the contiguity of any cograph is linearly bounded by the rank of its cotree T (Theorem 3.1 below) by using a path partition of T of minimal height h. Our proof is by induction on h and Lemma 3.1 below constitutes the recursive encoding step of our proof.

In a path partition of T , the path containing the root naturally induces a partition of the leaves of T , i.e. the vertices of the corresponding cograph G, as described in the following definition. A root-path decomposition (see Fig. 2) of a rooted tree T is a set {T 1 , . . . , T p } of disjoint subtrees of T , with p ≥ 2, such that every leaf of T belongs to some T i , with i ∈ [1..p], and the sets of parents in T of the roots of T i 's is a path containing the root of T . Lemma 3.1 (Caterpillar Composition Lemma). Given a cograph G = (V, E) and a root-path decomposition {T i } 1≤i≤p of its cotree, where X i is the set of leaves of

T i , cc(G) ≤ 2 + max i∈[1..p] cc(G[X i ]).
Sketch of proof. It is straightforward to check that for any i ∈ [1..p] and for any vertex x ∈ X i , the neighbors of x that are not in X i are split in at most two intervals in the order σ given on Fig. 3. Therefore, by choosing for σ an order on each X i that realizes the contiguity of G[X i ], we obtain that in σ, the neighborhood of any vertex x ∈ X i of G is split in at most 2 + cc(G[X i ]) intervals, which proves the lemma. A detailed version of this proof is given in Appendix B, in Lemma 5.3. 2 From this, we deduce an upper bound on the contiguity of a cograph depending on the rank of its cotree.

Sketch of proof.

The proof is by induction on rank(T ). The inequality holds for rank(T ) = 0. Consider a cograph G whose cotree T is of rank k + 1, with k ≥ 0. The nodes u of T such that rank(T u ) = k + 1 form a path containing only internal nodes of T and containing its root. Therefore, this path induces a root-path decomposition {T 1 , . . . , T p } of T as shown on Fig. 2. By definition, this root-path decomposition is such that for any i ∈ [1..p], tree T i is of rank at most k. Then, by the induction hypothesis, cc(G[X i ]) ≤ 2 rank(T i ) + 1. From Lemma 3.1, we have that cc(G)

≤ 2 + max i∈[1..p] cc(G[X i ]). It follows that cc(G) ≤ 2 + max i∈[1.
.p] {2 rank(T i ) + 1} ≤ 2 + 2k + 1 = 2(k + 1) + 1, which ends the induction and the proof of Theorem 3.1. A detailed version of this proof is given in Appendix B, in Theorem 5.3.

2

As the rank of a tree T is bounded by the logarithm of its number of leaves, we directly obtain the following corollary.

Theorem 3.2. If G = (V, E) is a cograph, then cc(G) ≤ 2 log 2 |V | + 1.

A lower bound for the contiguity of cographs

In this section, we show that the rank of a cotree also provides a lower bound on the contiguity of its associated cograph. Together with the result of the previous section, this give that the contiguity of a cograph and the rank of its cotree are mathematicaly equivalent functions, which is at the core of the approximation algorithm we present in next section. We also use the lower bound to exhibit a family of cographs on n vertices whose contiguity is at least Ω(log n), showing that the upper bound of the previous section is tight. Proof: We prove it by induction on k. We obviously have cc(G 0 ) ≥ 1. Now, suppose that cc(G k ) ≥ k + 1 for some k ≥ 0, and let us show that cc(G k+1 ) ≥ k + 2. Consider a cc(G k+1 )-interval-model of G k+1 , and denote by σ the corresponding order on the vertices of G.

We denote by r the root of T k+1 , and by v 1 , v 2 and v 3 its three children in T k+1 . Since there are at most two vertices of T k+1 that are next to r in σ, then there exists i ∈ 1, 3 such that no vertex of T k+1 v i is next to r in σ. Denoting by G v i the subgraph of G k+1 induced by the vertices of T k+1 v i , the induction hypothesis gives that cc(G v i ) ≥ k + 1. In particular, this implies that in the restriction of σ to the vertices of G v i , there exists some v ∈ G v i such that its neighborhood in G v i is split into at least k + 1 intervals. Since r is adjacent to v in G k+1 , and since the at most two vertices next to r in σ are not in the neighborhood of v, it follows that the neighborhood of v requires one more interval for r in σ. Thus, cc(G k+1 ) ≥ k + 2.

2 It is worth to note that G k is a cograph. Indeed, its cotree can be recursively built as follows. The cotree of G 1 (which is also known as the claw graph) is made of one series root having two children: a leaf and a parallel node having three leaf children. And replacing these three leaves by three copies of the cotree of G k , for any k ≥ 1, results in the cotree of G k+1 . From now on, in order to use the result of Theorem 2.2, we considered cotrees bicolored as explained in the following definition. The bicolored cotree of a cograph G is its cotree where the parallel nodes are colored black and the series nodes are colored white. Lemma 4.2. For any cograph G, whose bicolored cotree has a white root and black rank at least 2k, we have cc(G) ≥ k + 1.

Sketch of proof.

We prove by induction on k that G contains G k as an induced subgraph, which has contiguity at least k + 1 from Lemma 4.1. Since G has black rank at least 2k, its cotree T contains, as a minor, an entirely black complete binary tree T . Consider the two nodes at depth 1 in T , they have at least four different children in T . For three of them u 1 , u 2 and u 3 , take one leaf of their subcotree in T : since the nodes of T are all black (i.e. parallel), this gives three independent vertices denoted by x 1 , x 2 and x 3 . Now recall that the root of T is white (i.e. series) and must have a child which is not an ancestor of the root of T . Take a leaf y being a descendant of this child: y, x 1 , x 2 and x 3 induce the claw graph, i.e. the graph G 1 of Lemma 4.1.

Finally, note that for any u ∈ {u 1 , u 2 , u 3 }, u is necessarily white (as a parallel node of a cotree has only series, or leaf, children) and the cotree T u has black rank at least 2k -2. Then, from the induction hypothesis, the cograph associated to T u contains G k-1 as an induced subgraph. And from the recursive construction of the cotree of G k that precedes Lemma 4.2, we conclude that G contains G k as an induced subgraph.

A detailed version of this proof is given in Appendix C, in Lemma 5.5. 2

Theorem 4.1. For any cograph G and its cotree T , cc(G) ≥ (rank(T ) -7)/4.

Proof: Consider the bicolored cotree T of G. Then, from Lemma 2.2, r B (T ) + r W (T ) ≥ rank(T ) -1, so either r B (T ) ≥ (rank(T ) -1)/2, or r W (T ) ≥ (rank(T ) -1)/2. In the first case, r B (T ) ≥ 2((rank(T ) -3)/4) + 1, so T has a black complete binary tree of height 2((rank(T ) -3)/4), below a white node, as a minor, so Lemma 4.2 implies that cc(G) ≥ (rank(T ) -3)/4 + 1 ≥ (rank(T ) -7)/4.

In the second case, the bicolored cotree T Ḡ of the complement of G is simply the bicolored cotree of G where series and parallel nodes, and so black and white nodes, have been exchanged. Then, we have r B (T Ḡ) = r W (T ) ≥ (rank(T ) -1)/2. Lemma 4.2 implies similarly as above that cc( Ḡ) ≥ (rank(T )-3)/4+1. We can easily check that cc( Ḡ) ≤ cc(G)+2 (the closed neighborhood of any vertex x in Ḡ is composed by at most cc(G)+1 intervals surrounding the intervals of the closed neighborhood of x in G, plus possibly one interval for vertex x), so cc(G) ≥ (rank(T )-3)/4+1-2 = (rank(T )-7)/4. 2

From Theorem 4.1 we obtain that the contiguity of cographs is unbounded. Moreover, since the rank of a complete binary tree is, by definition, its height, it follows that the family of cographs having a complete binary cotree reaches the O(log n) upper bound of Theorem 3.2, showing that this bound is tight.

Corollary 4.1. For any cograph G whose cotree is a complete binary tree, cc(G) = Ω(log n).

As a direct consequence of Theorems 4.1 and 3.1, we obtain the equivalence between the contiguity of a cograph and the rank of its cotree, which is at the core of the approximation algorithm presented in next section.

Corollary 4.2. For any cograph G with cotree T , cc(G) = Ω(rank(T )).

An approximation algorithm for the contiguity of cographs

We now provide an algorithm that outputs an integer k and a k-interval-model of the cograph G given as input, such that k is in a constant ratio from the contiguity of G. Our algorithm takes as input a cograph G given by its cotree, which takes O(n) space, and outputs a k-interval model of G in O(kn) time, i.e. linear wrt. the size of the output. Alternatively, if only the value of k is needed, the algorithm runs in O(n) time, which is linear wrt. the size of the input.

First step: approximation of the contiguity of G. The first step of our algorithm computes an integer k which is in a constant ratio from the contiguity of G. To this purpose, we simply compute recursively the rank of T u for any node u ∈ T by a bottom-up process: for a node u we have either i) rank(T u ) = max v child of u rank(T v ) if this maximum is reached by only one child of u, or ii) rank(T u ) = 1 + max v child of u rank(T v ) otherwise. Then, our algorithm outputs the value k = 2 rank(T r ) + 1, where r is the root of T , and so rank(T r ) = rank(T ). This clearly takes O(n) time.

Furthermore, the approximation ratio ρ of this algorithm is constant. Using Theorem 4.1 and the fact that cc(G) ≥ 1, we deduce that ρ = (2 rank(T ) + 1)/cc(G) ≤ (2 rank(T ) + 1)/max(1, (rank(T ) -7)/4). This function reaches its maximum of 23 for rank(T ) = 11, and then the algorithm performs a 23-approximation of the closed contiguity (which can indeed be lower to 8 + , where is a positive constant as small as required, by using a constant-time precomputing step).

Second

Step: building a k-interval model of G. We follow the construction provided by Theorem 3.1 and Lemma 3.1 (see Fig. 3) in order to output a k-interval-model of G, where k = 2 rank(T )+ 1. During this process, we build the order σ on the vertices as well as a table N eighborhoods of n tables of 2k pointers to the bounds of the intervals of each vertex in order σ. To this purpose, we call the recursively defined routine Build(u), where u is a node of T , on the root r of T . Build(u) outputs an order σ u on the subset X u of vertices of G being the leaves of T u and table N eighborhoods u containing the pointers of the vertices of X u toward σ u . Routine Build(u) proceeds in three steps as follows. i) thanks to the ranks computed in the first step of the algorithm, Build(u) finds the subset P u of nodes ũ of T u such that rank(T ũ) = rank(T u ), and the subset C u of children in T of nodes ũ ∈ P u . ii) Build(u) recursively calls Build(v) for all nodes v ∈ C u . iii) Build(u) builds σ u by concatenating all the orders σ v returned by the recursive calls as shown on Fig. 3, and builds N eighborhoods u by merging all the tables N eighborhoods v returned by the recursive calls. Then, for each v ∈ C u and for each vertex x ∈ X v , we add to N eighborhoods u the pointers of x toward the at most two intervals of σ u formed by its neighbors that are not in X v , as explained in the proof of Lemma 3.1.

The terminal case of Routine Build(u) is when u is a leaf of T , for which the computation of σ u and N eighborhoods u is trivial and takes constant time. The fact that a call to Build(r) indeed gives the desired k-interval model of G comes from the fact that the routine follows the constructive proof of Theorem 3.1. Let us analyze its complexity. Step i), Step ii) and the construction of σ u in Step iii) take O(|C u | + |P u |), that is O(n) for the whole process on tree T . In Step iii), the merge of table N eighborhoods and the addition of the pointers to the two new intervals of each vertex take O(X u ) time. It turns out that, during the whole process on T , a vertex x will be involved in at most h different sets X u , where h is the height of the path partition of T defined by the set of paths P u computed along the process. From Theorem 3.1, h = rank(T ) = (k -1)/2. Thus, the total computation time of the k-interval model output by our algorithm is O(kn) time.

Conclusion

We showed that the contiguity of a cograph is equivalent to the maximum height of a complete binary tree contained in its cotree as a minor. From this, we obtained a tight O(log n) upper bound on the maximum contiguity of a cograph on n vertices. Even more interesting, this allowed us to design a linear time algorithm that does not only compute an approximation of the contiguity of a cograph G but also provides a k-interval model realizing a k which is in a constant-ratio to the optimal one, i.e. the contiguity of G. Then, the first question raised by our work is whether it is possible to compute efficiently the exact value of the contiguity of a cograph and to provide a model realizing this optimal value. Another key perspective is to extend our results to larger classes of graphs, such as permutation graphs (which are a proper generalization of cographs) and interval graphs. Does the O(log n) upper bound still hold for those graphs? Is it possible to compute efficiently an exact or approximated value of their contiguity? contractions. The partition P we build is induced from P in the sense that we obtain it by updating partition P step by step along the series of edge contractions of T resulting in T . Along this process, when an edge uv of the current tree T cur , where u is the parent of v, is contracted in order to obtain the next tree T next , we delete node v and assign its children to u, as in Definition 1.1 and as shown in Figure 5. This ensures that any set P of nodes inducing a path in T cur also induces a path in T next (except in the case where P = {v}: P becomes the empty set after the contraction and disappears from the path partition we maintain). Consequently, a path partition P next of T next can be obtained from the partition P cur of T cur in the following way: for all the nodes remaining in T next (i.e. all the nodes of T cur except node v), we keep them in the same path of the partition as they were previously belonging to in P cur .

It is not difficult to see that the partition tree T next p of P next defined this way has height at most that of T cur p . Indeed, from the definition of the partition tree (see the beginning of Section 2), during the contraction of edge uv, the only paths of P cur that are likely to change their parent in T next p are those paths whose root is one of the children of v, as the other nodes of T cur do not change their parent. For such a path P v rooted at a child v of v, the parent of P v in T next p will be the path P u containing u, which may be either its parent or its grandparent in T cur p , depending on whether nodes u and v are in the same path of P cur or not. Since the only nodes of T cur p that change their parents in T next p change it for their grandparent in T cur p , it follows that h(P next ) ≤ h(P cur ). Consequently, at the end of the series of edge contractions that results in T , we obtain a path partition P of T such that h(P ) ≤ h(P). As this holds for any path partition P of T , we conclude that ph(T ) ≤ ph(T ).

≥ : We show that rank(T ) ≥ ph(T ) by induction on rank(T ). We use the following induction hypothesis H(k): "for any tree T such that rank(T ) = k, we have ph(T ) ≤ rank(T )".

Clearly, if rank(T ) = 0, then T is a rooted path. Thus, there is a trivial partition of T into a single path and the path-height of this partition is 0 : ph(T ) ≤ rank(T ). Now, let k ≥ 0 such that ∀i ∈ 0, k , H(k) holds. We show that H(k + 1) is satisfied. Let T be a tree such that rank(T ) = k +1, and let S k+1 be the subset of nodes u of T such that rank(T u ) = k +1. We first show that S k+1 is a path of T containing the root.

Clearly, by definition of rank(T ), S k+1 contains the root of T , so let us show that it induces a path of T . First, note that if u is such that rank(T u ) = k + 1 then for all ancestors v of u, rank(T v ) = k + 1. Indeed, it is clear that rank(T v ) is not less than rank(T u ), and since rank(T ) = k + 1, we also have rank(T v ) ≤ k + 1. Now, assume for contradiction that there exist two nodes u, v ∈ S k+1 such that none of them is the ancestor of the other. Let w be the least common ancestor of u and v in T . Let u and v be the two distinct children of w that are the ancestors of respectively u and v. From above, u and v are such that rank(T u ) = rank(T v ) = k + 1. It follows that rank(T w ) ≥ k + 2: contradiction. Thus, all the nodes of S k+1 are comparable for the ancestor relationship, and since we Sketch of proof. We prove it by induction. The result is obvious for k = 1. Now, let us fix k ≥ 1, and consider a cograph G whose bicolored cotree T has black rank at least 2(k + 1). Then it contains the complete binary tree T B of height 2(k + 1), and each vertex of T B can be mapped to one vertex of T : as T B is a minor of T , among all vertices of T which were contracted into one vertex y of T B , we choose one (also colored black), and also name it y. Thus, we label some vertices of T B as illustrated in Figure 6: u is the root and its children are called u 1 and u 2 . The two children of u 1 are called w 1 and w 2 and one child of u 2 is called w 3 . We give the same labels to the mapped vertices in T , and add the following ones: r is the white root of T , v is a black child of r which is not an ancestor of u, and v 1 , v 2 , v 3 are the respective white parents of w 1 , w 2 , w 3 . Finally, we denote by X 1 , X 2 , X 3 the set of leaves of respectively T v 1 , T v 2 , T v 3 and by x be a leaf of T v .

Vertex x is adjacent in G to all the vertices of X 1 ∪ X 2 ∪ X 3 , and for any distinct i, j in 1, 3 , all the vertices of X i are non-adjacent to all the vertices of X j . Moreover, T v 1 , T v 2 , T v 3 are trees with a white root, and black rank at least 2k. So we apply the induction hypothesis, and cc(G[X i ]) ≥ k for any i ∈ 1, 3 .

Consider a linear order σ on the vertices of G. We denote by a (resp. b) the vertex of X 1 ∪ X 2 ∪ X 3 which is closer to x on the left resp. on the right) in σ, if it exists (i.e. if there is some node of X 1 ∪ X 2 ∪ X 3 on the left (resp. right) of x in σ). Clearly, there exists i ∈ 1, 3 such that none of a, b is in X i . Then, for all the vertices y ∈ X i , there exists some vertex z ∈ {a, b} such that z is between x and y in σ, and z is not adjacent to y. Since X i has contiguity at least k, there exists some vertex y 1 ∈ X i such that its neighborhood in G[X i ] is split in at least k intervals in σ. Furthermore, since y 1 is adjacent to x but all the vertices of X i are separated from x in σ by some z ∈ {a, b} which is not adjacent to y 1 , then it follows that the neighborhood of y 1 is split in at least k + 1 intervals in σ. Thus, cc(G) ≥ k + 1, which ends the proof.

2

Fig. 1 .

 1 Fig. 1. A tree T and a path partition P = {P1, P2, P3, P4, P5, P6} of T (a), as well as the partition tree of P (b).

Fig. 2 .

 2 Fig. 2. The root-path decomposition {T1, . . . , Tp} of a rooted tree T .

Fig. 3 .

 3 Fig. 3. The general structure of the order σ used in Lemma 3.1 for the root-path decomposition of Fig 2.

Theorem 3 . 1 .

 31 For any cograph G having cotree T , cc(G) ≤ 2 rank(T ) + 1.

Lemma 4 . 1 .

 41 Let G k be the underlying undirected graph of the transitive closure of the directed rooted complete ternary tree T k of depth k ≥ 0. Then, we have cc(G k ) ≥ k + 1.

Fig. 5 .

 5 Fig. 5. Left: a tree Tcur with its path partition Pcur = {P1, P2, P3, P4, P5, P6} whose partition tree T cur p has height 2. Right: the tree Tnext resulting from the contraction of edge uv in Tcur, together with its path partition Pnext = {P 1 , P 2 , P 3 , P 4 , P 5 , P 6 }. All the paths in Pnext are the same as those in Pcur, except P 5 which has lost node v. The height of T next p

Fig. 6 .

 6 Fig.6. The cotree T of black rank 2(k + 1) used in the proof of Lemma 4.2, and the associated black complete binary tree TB of height 2(k + 1).

Acknowledgments. The authors thank Pierre Charbit and Stéphan Thomassé for useful discussions on the subject, as well as George Oreste Manoussakis for proofreading a draft of this article. This work was partially supported by the PEPS-C1P CNRS project.

Appendix

Appendix A) Some useful results on trees

We formally state and prove the claim in the end of Section 1 that "the closed and open contiguity never differ by more than one". Lemma 5.1. For any graph G, cc(G) ≤ oc(G) + 1 and oc(G) ≤ cc(G) + 1.

Proof: If we have an open k-interval-model for G based on order σ, we can make a closed k-intervalmodel of G by simply adding one interval for vertex x, when we are encoding the closed neighborhood of x by a union of intervals, so cc(G) ≤ oc(G) + 1.

For the second inequality, if we have a closed k-interval-model, removing vertex x from the union of intervals encoding its neighborhood will, in the worst case, break one interval (the one containing x) into two, and therefore it may cost up to one more interval. So oc(G) ≤ cc(G) + 1 2 We now give the details of the proof of Theorem 2.1. To this purpose, we first prove the result on rooted complete binary trees. Lemma 5.2. For any rooted complete binary tree T , rank(T ) = ph(T ) = h(T ).

Proof: The fact that h(T ) = rank(T ) is obvious from the definition of rank(T ). On the other hand, one can build a path partition P of height h(T ) by taking P = {{x}} x∈V (T ) . In other words, each path in P is reduced to one single vertex of T . In this way, T p (P) = T wich gives ph(T ) ≤ h(T ).

Conversely, we prove that ph(T ) ≥ h(T ) by induction on h(T ). This property is true for the trivial tree T with only one vertex, for which we have ph(T ) = 0 ≥ 0 = h(T ). Now, assume that it is true for any rooted complete binary tree of height k ≥ 0, and consider a rooted complete binary tree T of height k + 1. Let P be a path partition of T such that h(P) = ph(T ), and let P be the path of P containing the root r of T , as shown in Figure 4.

Fig. 4. The induction step of the proof that the path-height of a complete binary tree is at least as big as its height, in the proof of Lemma 5.2.

The path P does not contain at least one child u of r. Then, the subset P of P made of those paths containing some node of T u is a path partition of T u . And from the induction hypothesis, we get h(P ) ≥ ph(T u ) ≥ h(T u ) ≥ k. Since h(P) ≥ h(P ) + 1, we obtain h(P) ≥ k + 1, and so ph(T ) ≥ k + 1. This ends the induction and the proof of Lemma 5.2. 2

Theorem 5.1. For any rooted tree T , rank(T ) = ph(T ).

Proof: ≤ : Let T be a complete binary tree which is a minor of T of maximum height among such complete binary trees. By definition, we have rank(T ) = h(T ) and from Lemma 5.2 we know that h(T ) = ph(T ). It follows that rank(T ) = ph(T ). Then, in order to prove rank(T ) ≤ ph(T ), we show that ph(T ) ≤ ph(T ). Indeed, consider an arbitrary path partition P of T . We will build a path partition P of T whose height is at most the height of P. By definition, tree T can be obtained from T by a series of edge already showed that all the ancestors of a node in S k+1 are in S k+1 , it follows that S k+1 induces a path of T containing the root. Now, let S = {u ∈ V (T ) \ S k+1 | parent(u) ∈ S k+1 }, and let u ∈ S . Clearly, since u ∈ S k+1 , rank(T u ) ≤ k and the induction hypothesis implies that ph(T u ) ≤ k. For any u ∈ S , we denote by P u a path partition of T u of height at most k. Then, {S k+1 } ∪ u∈S P u is a path partition of T and has height at most k + 1. Thus, ph(T ) ≤ k + 1 = rank(T ) and H(k + 1) holds, which ends the induction, showing that for any tree T , rank(T ) ≥ ph(T ). 2

Theorem 5.2. For any bicolored complete binary tree T , r B (T ) + r W (T ) ≥ h(T ) -1.

Proof: We prove it by induction on h(T ). This clearly holds for h = 1. Suppose the property holds for some h ≥ 1, and let T be a complete binary tree of height h + 1. We show that the properties also hold for T . T is made of a root r with two children subtrees T a and T b . Let us assume wlog that the root of T is colored black.

If

and the property is satisfied.

On the other hand, if

Appendix B) An upper bound for the contiguity of cographs Lemma 5.3 (Caterpillar Composition Lemma). Given a cograph G = (V, E) and a root-path decomposition {T i } 1≤i≤p of its cotree,

where X i is the set of leaves of T i .

Proof: For convenience of description of the closed contiguity model of G, we assume wlog. that the T i 's are numbered in such a way that for any i, j ∈ 1, p , if the parent of the root of T i is a strict ancestor of the parent of the root of T j then i > j. Moreover, we color the trees T i of the root-path decomposition in the following way: if the root of T i is a series node, T i is colored white, otherwise T i is colored black. Let σ i be a closed contiguity model realizing the closed contiguity of G[X i ], where X i is the set of leaves of T i . We now build an order σ on the vertices of G such that for each x ∈ V (G), N [x] is the union of at most l + 2 intervals of σ, where l = max i∈ 1,p cc(G[X i ]), which proves the lemma.

For clarity in the description of σ, we denote by σ i + σ j the concatenation of the orders σ i and σ j , which allows us to use the sum notation i=1 to p σ i = σ 1 + σ 2 + . . . + σ p . Beware that in the case of the concatenation operation, the sum is not commutative: it must be done in the specified order, from 1 to p. Then the order σ we build is simply defined as (see Figure 3):

We now prove that, in σ, the closed neighborhood N [x] of any vertex x ∈ V (G) is split in at most l + 2 intervals. We separate the case where x is a leaf of some white T i from the case where x is a leaf of some black T i .

In the former case, the neighbors of x that are not in T i are exactly those vertices belonging to some black X j such that j > i. Then, we have N [x] = (N [x] ∩ X i ) ∪ j>i and X j is black X j . As σ i realizes the closed contiguity of G[X i ], which is by definition at most l, N [x] ∩ X i is split in at most l intervals in σ i . And since j>i and X j is black X j is an interval of σ, it follows that N [x] is split in at most l + 1 intervals in σ. Now consider the case where x is a leaf of some black T i . The neighbors of x that are not in T i are exactly those vertices belonging to some black X j , j = i, or belonging to some white X j such that j < i. Then, we have N [x] = (N [x] ∩ X i ) ∪ ( j<i, X j black X j ) ∪ ( j>i, X j black X j ∪ j <i, X j white X j ). Again, from the definition of σ i , N [x]∩X i is split in at most l intervals in σ i . Moreover, j<i, X j black X j and j>i, X j black X j ∪ j <i, X j white X j are two intervals of σ. Thus, N [x] is split in at most l + 2 intervals in σ. As this holds for any vertex x in G, it follows that cc(G) ≤ 2 + l, which ends the proof of the lemma.

2 To give a detailed proof of Theorem 3.1, we actually start by proving the following Lemma.

Lemma 5.4. Given a rooted tree T such that rank(T ) = k ≥ 1, there exists a root-path decomposition {T 1 , . . . , T p } of T such that for each i ∈ 1, p , rank(T i ) ≤ k -1.

Proof: Since T has rank k, from Theorem 2.1, T has path-height k. Consider a path partition P of T of height k where the path containing the root r of T is denoted by P r . If the lowest node of P r is a leaf, removing it from P r and letting it form its own path still gives a path partition of height k, since k ≥ 1. We thereby assume that P r contains only internal nodes of T . We denote by u 1 , . . . , u p the nodes of T whose parent is in P r . Clearly, for each i ∈ 1, p , the paths of P that contain some node of T u i form a path partition P i of T u i . And since P has height k, then for all i ∈ 1, p , P i has height at most k -1. It follows from Theorem 2.1 that rank(T u i ) ≤ k -1. Thus, {T u 1 , . . . , T up } is a suitable root-path decomposition of T , which achieves the proof of the lemma. 2

Theorem 5.3. For any cograph G and its cotree T , cc(G) ≤ 2 rank(T ) + 1.

Proof: We prove this property by induction on the rank k of T . For k = 1, we have to show that cc(G) ≤ 3. Since T is a cotree, all its internal nodes have at least two children. It follows, since T has rank 1, that all its internal nodes are ancestors of each other, otherwise T would have rank at least 2. Thus, T is a rooted caterpillar, i.e. a rooted tree where all internal nodes are ancestors of the lowest nodes of the tree. Let us denote V (G) = {x i } 1≤i≤n . Since T is a caterpillar, the family {T i } 1≤i≤n , where T i is the trivial tree formed with the single leaf x i , is a root-path decomposition of T . With the notations of Lemma 3.1, the set of leaves of T i is X i = {x i }.

And since for any

Now, let k ≥ 1 such that the property holds for all k ∈ 1, k , that is any cograph G whose cotree T has rank k satisfies cc(G) ≤ 2 rank(T ) + 1. We prove this also holds for k + 1. Let T be the cotree of a cograph G such that rank(T ) = k + 1. From Lemma 5.4, there exists a root-path decomposition {T 1 , . . . , T p } of T such that for all i ∈ 1, p , rank(T i ) ≤ k. Thus, by applying the induction hypothesis on each T i , we know that ∀i ∈ 1, p , cc(G[X i ]) ≤ 2 rank(T i ) + 1 ≤ 2k + 1, where X i is the set of leaves of T i . By applying Lemma 3.1, we deduce that cc(G) ≤ 2+max i∈ 1,p cc(G[X i ]) ≤ 2k +3 = 2(k +1)+1. This ends the induction and the proof of the Lemma. 2


Florian Kaiser

Thomas Coudreau

Perola Milman

Daniel B Ostrowsky

Sébastien Tanzilli
email: sebastien.tanzilli@unice.fr

Entanglement-enabled delayed choice experiment

Wave-particle complementarity is one of the most intriguing features of quantum physics. To emphasize this measurement apparatus dependent nature, experiments have been performed in which the output beam-splitter of a Mach-Zehnder interferometer is inserted or removed after a photon has already entered the device. A recent extension suggested using a 'quantum beam-splitter' at the interferometer's output. We realize this using pairs of polarization entangled photons. One photon is tested in the interferometer and is detected, while the other allows determining whether wave, particle, or intermediate behavior have been observed. Furthermore, this allows continuously morphing the tested photon's behavior from wave like to particle like. This illustrates the inadequacy of a naive wave or particle description of light.

While the predictions of quantum mechanics have been verified with remarkable precision, subtle questions arise when attempting to describe quantum phenomena in classical terms [START_REF] Schrödinger | Die gegenwärtige Situation in der Quantenmechanik[END_REF][START_REF] Greenstein | The Quantum Challenge: Modern Research On The Foundations Of Quantum Mechanics[END_REF].

For example, a single quantum object can behave as a wave or as a particle, which is illustrated by Bohr's complementarity principle [START_REF] Bohr | Quantum Theory and Measurement[END_REF]. It states that, depending on the measurement apparatus, either wave or particle behavior is observed [START_REF] Kim | Delayed choice quantum eraser[END_REF][START_REF] Walborn | Double-slit quantum eraser[END_REF]. This is demonstrated by sending single photons into a Mach-Zehnder interferometer (MZI) followed by two detectors (6) (Fig. 1A).

If the MZI is closed, i.e. the paths of the interferometer are recombined at the output beamsplitter (BS 2 ), the probabilities for a photon to exit at detectors D a and D b depend on the phase difference θ between the two arms. The which-path information remains unknown, and wavelike intensity interference patterns are observed (Fig. 1B). On the other hand, if the MZI is open, i.e. BS 2 is removed, each photon's path can be known and, consequently, no interference occurs. Particle behavior is said to be observed and the detection probabilities at D a and D b are equal to 1 2 , independently of the value of θ (Fig. 1C). In other words, these two different configurations, i.e. BS 2 present or absent, give different experimental results. Recently it has been shown that, even when performing Wheeler's original gedanken experiment [START_REF] Wheeler | Quantum Theory and Measurement[END_REF], in which the configuration for BS 2 is chosen only after the photon has passed the entrance beam-splitter BS 1 , Bohr's complementarity principle is still obeyed [START_REF] Jacques | Experimental Realization of Wheeler's Delayed-Choice Gedanken Experiment[END_REF]. Intermediate cases, in which BS 2 is only partially present, have been considered in theory and led to a more general description of Bohr's complementarity principle expressed by an inequality limiting the simultaneously available amount of interference (signature of wave-like behavior) and which path information (particle-like behavior) [START_REF] Wootters | Complementarity in the double-slit experiment: Quantum nonseparability and a quantitative statement of Bohr's principle[END_REF][START_REF] Englert | Fringe Visibility and Which-Way Information: An Inequality[END_REF]. This inequality has also been confirmed experimentally in delayed choice configurations [START_REF] Jacques | Delayed-Choice Test of Quantum Complementarity with Interfering Single Photons[END_REF][START_REF] Tang | Realization of quantum Wheeler's delayedchoice experiment[END_REF].

We take Wheeler's experiment one step further by replacing the output beam-splitter by a quantum beam-splitter (QBS), as recently proposed theoretically [START_REF] Ionicioiu | Proposal for a quantum delayed-choice experiment[END_REF][START_REF] Schirber | Another Step Back for Wave-Particle Duality[END_REF]. In our realization (Fig. 2), we exploit polarization entanglement as a resource for two reasons. First, doing so per-mits implementing the QBS. Second, it allows us to use one of the entangled photons as a test photon sent to the interferometer, and the other one as a corroborative photon. Here, as opposed to previous experiments [START_REF] Jacques | Experimental Realization of Wheeler's Delayed-Choice Gedanken Experiment[END_REF][START_REF] Jacques | Delayed-Choice Test of Quantum Complementarity with Interfering Single Photons[END_REF], the state of the interferometer remains unknown, and therefore the wave or particle behavior of the test photon, until we detect the corroborative photon.

By continuously modifying the type of measurement performed on the corroborative photon, we can morph the test photon from wave to particle behavior, even after the test photon was detected. To exclude interpretations based on either mixed states, associated with pre-existing state information [START_REF] Einstein | Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?[END_REF], or potential communication between the two photons, the presence of entanglement is verified via violation of the Bell inequalities with a space-like separation [START_REF] Bell | On the Einstein-Podolsky-Rosen Paradox[END_REF][START_REF] Aspect | Experimental Test of Bell's Inequalities Using Time-Varying Analyzers[END_REF][START_REF] Weihs | Violation of Bell's Inequality under Strict Einstein Locality Conditions[END_REF].

The QBS is based on the idea that when a photon in an arbitrary polarization state enters an interferometer that is open for |H (horizontally polarized) and closed for |V (vertically polarized) photons, the states of the interferometer and the photon become correlated. Our apparatus, shown in the right hand side of Fig. 2 and detailed in Fig. S1, therefore reveals a particle behavior for the |H component of the photon state, and a wave behavior for the |V component. Note that such an experiment has been realized using single photons prepared in a coherent superposition of |H and |V [START_REF] Tang | Realization of quantum Wheeler's delayedchoice experiment[END_REF]. However, we take this idea a step further by achieving genuine quantum behavior for the output beam-splitter by exploiting an intrinsically quantum resource, entanglement. This allows entangling the quantum beam-splitter and test photon system with the corroborative photon. Thus, measurement of the corroborative photon enables projecting the test photon/QBS system into an arbitrary coherent wave-particle superposition, which is a purely quantum object. In other words, our QBS is measured by another quantum object, which projects it into a particular superposition of present and absent states.

More precisely, we use as a test photon one of the photons from the maximally polarization entangled Bell state,

|Φ + = 1 √ 2 c † H t † H + c † V t † V |vac
, produced at the wavelength of 1560 nm using the source described in [START_REF] Kaiser | Guided-wave photonics for narrowband polarization entanglement[END_REF]. Here, using the notation of Fig. 2,c †

H (t † H ) and c † V (t † V ) rep-
resent creation operators for horizontally and vertically polarized photonic modes, respectively, propagating towards the corroborative (test) photon apparatus. Moreover, |vac represents the vacuum state. Using an entangled state of this form ensures maximum randomness of the input polarization state of the test photon (t), which enters a Mach-Zehnder interferometer with a QBS for the output beam-splitter.

The actual QBS device is made up of two components. The first is a polarization dependent beam-splitter (PDBS) that shows close to 100% reflection for horizontally polarized photons and provides ordinary 50/50 splitting ratio for the vertically polarized photons. The PDBS is realized using a combination of standard bulk optical components as described in supplementary information S1. The whole state after the PDBS reads

|Ψ = 1 2 c † H -e i θ a † H + i b † H + + 1 √ 2 c † V b † V (i + i e i θ ) + a † V (1 -e i θ ) |vac . (1)
Here, θ is an adjustable phase shift in the interferometer, while a † H , a † V , b † H , and b † V symbolize creation operators for test photons propagating toward PBS 1 and PBS 2 , respectively. At this point, each polarization state of the test photon is associated with one of the two complementary types of behaviors, wave and particle.

The second stage consists of polarizing beam-splitters (PBS 1 and PBS 2 ) oriented at 45 • to the {H, V } basis, that permits erasing all polarization information that existed at the PDBS output [START_REF] Kim | Delayed choice quantum eraser[END_REF][START_REF] Walborn | Double-slit quantum eraser[END_REF][START_REF] Herzog | Complementarity and the quantum eraser[END_REF]. Eq. 1 becomes

|Ψ = 1 √ 2 c † H [particle] † + c † V [wave] † |vac , (2)
with

[particle] † = 1 2 -e i θ (a ′ † + a ′′ † ) + i(b ′ † + b ′′ † ) ,
and

[wave] † = 1 2 √ 2 (1 -e i θ )(-a ′ † + a ′′ † ) + i(1 + e i θ )(-b ′ † + b ′′ † ) .
Here, the creation operators a ′ † , a ′′ † , b ′ † and b ′′ † denote photons propagating toward detectors D a ′ , D a ′′ , D b ′ and D b ′′ , respectively. Consequently, the only way of knowing if wave or particle behavior was observed is by examining the corroborative photon.

The corroborative photon measurement apparatus, as shown on the left-hand side of Fig. 2.

consists of two stages. The first is an electro-optic phase modulator (EOM) that allows rotating the polarization state of the corroborative photon by an angle α. From Eq. 2, we now have

|Ψ = 1 √ 2 c † H (cos α[particle] † -sin α[wave] † ) + c † V (cos α[wave] † + sin α[particle] † ) |vac . (3)
After passing PBS 3 , that is oriented on the {H, V } axis, the corroborative photon is transmitted (test), where ⊕ denotes an exclusive OR (XOR) gate, are In this case, for all the four correlation functions mentioned above, the configuration of the interferometer remains undetermined even after the test photon has been detected. In other words, there is no information available yet from the corroborative photon that could influence the behavior of the test photon. Furthermore, a space-time analysis shows that no classical communication can be established between the photon detection events, as they are space-like separated (Fig. 3).

I H,b (θ, α) = cos 2 θ 2 sin 2 α + 1 2 cos 2 α. (4)
We now measure the correlations between detectors D H and [D b ′ ⊕ D b ′′ ] via counting coincidence events on the corresponding single photon detectors (InGaAs avalanche photodiodes).

As shown in Fig. 4(A), the experimentally measured results are in near perfect agreement with the theoretical predictions of Eq. 4. For the angle α = 0 • , I H,b (θ, 0) is independent of the phase θ as predicted for particle-like behavior. Setting α = 90 • results in sinusoidal intensity oscillations as a function of θ, which corresponds to wave-like behavior. For 0 • < α < 90 • , a continuous transition from wave to particle behavior is observed, expressed by the continually reducing fringe visibility. As outlined in references (9, 10), a generalization of Bohr's complementarity principle implies the interference fringe visibility V and the path distinguishability D, also called the which-way information, to be limited by the following inequality

V 2 + D 2 ≤ 1. (5)
The experimental measurement of these two quantities is described in supplementary information S2 [START_REF] Jacques | Delayed-Choice Test of Quantum Complementarity with Interfering Single Photons[END_REF][START_REF] Tang | Realization of quantum Wheeler's delayedchoice experiment[END_REF]. Fig. 4(B) shows the obtained results for V 2 , D 2 and V 2 + D 2 as a function of the angle α. With our experimental data, Eq. 5 is confirmed for all angles of α.

To prove the existence of a coherent quantum superposition of wave and particle behavior of the test photon created by the detection of the corroborative photon, the presence of entanglement needs to be verified [START_REF] Bell | On the Einstein-Podolsky-Rosen Paradox[END_REF][START_REF] Clauser | Proposed experiment to test local hidden-variable theories[END_REF]. Note that several recent realizations ignored this and therefore the presence of a QBS has not been proven unambiguously [START_REF] Roy | NMR implementation of a quantum delayed-choice experiment[END_REF][START_REF] Auccaise | Experimental analysis of the quantum complementarity principle[END_REF]. In our realization, entanglement is proven by performing the same experiment as before, but using the complementary analysis basis, namely the diagonal basis {D, A}. Now, the initial quantum state is rotated by 45 We note that the detection loophole remains open in our experiment, since some of the initial entangled photons are lost during their propagation in the fiber or bulk channels, or are not detected by the single photon detectors that show non-unit quantum detection efficiencies [START_REF] Clauser | Experimental consequences of objective local theories[END_REF].

• , i.e. 1 √ 2 c † V t † V + c † H t † H |vac → 1 √ 2 c † D t † D + c † A t † A |vac ,
We therefore make the reasonable assumption that the detected photons represent a faithful sample [START_REF] Aspect | Experimental Test of Bell's Inequalities Using Time-Varying Analyzers[END_REF].

In conclusion, we have carried out a quantum delayed choice experiment, enabled by polarization entangled photons and the associated property of non-locality. We used a Mach-Zehnder interferometer where the output beam-splitter has been replaced by its quantum analogue, i.e. a beam-splitter in a coherent superposition of being present and absent. In this configuration, we observed that the single photons under test can indeed behave as waves and particles in the same experiment, meaning that the simple view of photons being either waves or particles is refuted.

We experimentally excluded interpretations based on local hidden variables and/or information exchange between the photon and the quantum beam-splitter. The state of the quantum beam-splitter is determined by the detection of the corroborative photon. We have, therefore, demonstrated interference between wave and particle behavior, which underlines the subtleness of Bohr's complementarity principle.

We note that, parallel to this work, Peruzzo et al. realized another version of a quantum delayed choice experiment based on entangled photons [START_REF] Peruzzo | A quantum delayed choice experiment[END_REF]. from both photon detection events do not overlap, demonstrating that space-like separation is of 350 events/5 s. The noise contribution, on the order of 3 events/5 s, has not been subtracted.

Figures (B) and (D) represent plots and related sinusoidal fits (solid lines) of the fringe visibility V (black) and path distinguishability D (red) as a function of the angle α. For all angles, we verify V 2 + D 2 ≤ 1 as predicted by Eq. 5, the blue solid line being a guide for the eyes. Note that the same experimental results would be obtained if the timing order of the measurements of the test and corroborative photons would be inverted [START_REF] Ma | Experimental delayedchoice entanglement swapping[END_REF].

D is measured for fixed angles α using the following procedure.

(

  |H ) or reflected (|V ). This projects the test photon into a state defined by the terms in the parentheses of Eq. 3. Therefore, the firing of detector D H indicates that the test photon is in the state cos α[particle] † -sin α[wave] † , while the firing of D V that it is in the state cos α[wave] † + sin α[particle] † . It can be seen that by choosing 0 < α < 90 • , a continuous morphing between wave and particle behavior is obtained. The expected intensity correlations, given by the coincidence count probability between detectors D H (corroborative) and [D b ′ ⊕D b ′′ ]

  Note that the correlations between detectors D V and [D a ′ ⊕ D a ′′ ] follow the same function. On the contrary the complementary intensity correlations, i.e. between detectors D H and[D a ′ ⊕D a ′′ ] or between D V and [D b ′ ⊕ D b ′′ ], are given by 1 -I H,b (θ, α).The use of XOR gates permits counting the photons from both outputs of each quantum eraser (PBS 1 or PBS 2 ), and reaching an average coincidence rate of 70/s for each of them. Note that Eq. 4 does not depend on the relative detection times of the two photons. In the experiment reported here, the detection of the corroborative photon is delayed until after the detection of the test photon. This is ensured by inserting an extra 5 m length of optical fiber in the path of the corroborative photon (c).

  where D and A symbolize diagonally and anti-diagonally polarized photon contributions, respectively. In this configuration, every single photon is unpredictably subjected to a closed or open Mach-Zehnder configuration by the PDBS. In this case, as opposed to the experiment in the {H, V } basis, if a statistical mixture was analysed instead of an entangled state, no correlations should be observed when measuring I H,b (θ, α). However, the strong correlations shown in Fig.4(C) exclude a statistical mixture and are in good agreement with the theoretical predictions of Eq. 4. This underlines that wave and particle behavior coexist simultaneously for the entire range 0 • < α < 90 • in the {H, V } basis, and for -45 • < α < 45 • in the {D, A} basis. Fig.4(D) shows the measurements for V 2 , D 2 and V 2 + D 2 as a function of α and confirms the upper limits imposed by Eq. 5.The quality of the entangled state is measured via the Bell parameter S, which is deduced from the phase oscillation visibilities at α = 90 • in the {H, V } basis, and α = 45 • in the {D, A} basis. We obtain S = 2.77 ± 0.07, which is very close to the optimal value of 2 √ 2 attained with maximally entangled states, and 11 standard deviations above the classical/quantum boundary S = 2[START_REF] Bell | On the Einstein-Podolsky-Rosen Paradox[END_REF][START_REF] Clauser | Proposed experiment to test local hidden-variable theories[END_REF].

Fig. 1 :

 1 Fig. 1: (A) -Wheeler's gedanken experiment using a Mach-Zehnder interferometer. The device consists of two beam-splitters, BS 1 and BS 2 , a glass plate introducing a phase shift θ, and two detectors, D a and D b , at its output. (B) -Simulated photon detection probabilities at detectors D a and D b as a function of the phase θ. The sinusoidal oscillations are related to unknown path information, and therefore to single photon interference, which is a wave-like phenomenon. (C) -Detection probabilities without BS 2 . No interference is observed, which is the signature of particle behavior.

Fig. 2 :Fig. 3 :

 23 Fig. 2: Experimental setup. A source of polarization entangled photons (λ = 1560 nm, see[START_REF] Ionicioiu | Proposal for a quantum delayed-choice experiment[END_REF]

  First, the interferometer path a is blocked and the coincidence probabilities p aa between detectors D H and (D a ′ ⊕ D a ′′ ) and p ab between detectors D H and (D b ′ ⊕ D b ′′ ) are recorded. Here, the first subscript denotes the blocked interferometer arm and the second which detector combination is used. We then compute D a = (|p aa -p ab |)/(p aa + p ab ). Note that complete path distinguishability leads to p aa = 0 and p ab = 1, resulting in D a = 1. The same measurement is repeated when interferometer path b is blocked, giving the probabilities ba , p bb , and consequently D b = (|p bap bb |)/(p ba + p bb ). We finally calculate the average D = (D a + D b )/2, which drops to zero for wave-like behavior and is unity for particle-like behavior.

We thank L. A. Ngah for his help on data acquisition and O. Alibart for fruitful discussions. Supported by the CNRS, l'Université de Nice -Sophia Antipolis, l'Agence Nationale de la Recherche for the 'e-QUANET' project (grant ANR-09-BLAN-0333-01), the European ICT-2009.8.0 FET open program for the 'QUANTIP' project (grant 244026), le Ministère de l'Enseignement Supérieur et de la Recherche (MESR), la Fondation iXCore pour la Recherche, and le Conseil Régional PACA for the 'QUANET' project.

achieved. In other words, no causal connection between these events can be established.

S2: Measurement of fringe visibility and path distinguishability

The interference fringe visibility V shown in Fig. 4(B,D) is measured as follows. The angle α is fixed and the maximum (p max ) and minimum (p min ) fitted coincidence probabilities are determined as a function of θ. We then compute V = (p max -p min )/(p max + p min ).