domain: phys spi

text:
Aeroacoustic Computations

A Suss

I Mary

T Le Garrec

S Marié

EXTENDED COMPARISON BETWEEN LATTICE BOLTZMANN AND NAVIER-STOKES SOLVERS FOR UNSTEADY AERODYNAMIC AND

INTRODUCTION

Within the past decades, Computational Fluid Dynamics (CFD) has dramatically risen in the aerospace industry enabling the simulation of configurations of growing complexity. The increasing computational power and the growing need of high-fidelity methods owing to new sustainable aviation objectives have lead to the development of Large Eddy Simulations (LES). As indicated by Löhner [START_REF] Löhner | Towards overcoming the LES crisis[END_REF], structured finite-type Navier-Stokes (NS) methods and lattice Boltzmann methods (LBM) may be the first to achieve industrial-level LES.

While LES or hybrid RANS-LES applied to the Navier-Stokes equations are well established and studied approaches, the LBM, which relies on a mesoscopic description of collisions between fluid particles, has gradually emerged as an interesting alternative for the LES of weakly compressible flows [START_REF] Touil | Direct and large-eddy simulation of turbulent flows on composite multi-resolution grids by the lattice Boltzmann method[END_REF]. Consequently, one question which naturally arises is: Which method is the most competitive, in terms of accuracy and computational cost, on canonical aerodynamic and aeroacoustic applications ? Previous work on the comparison between the LBM and traditional NS methods focused on different topics such as convergence order [START_REF] Noble | Comparison of accuracy and performance for lattice Boltzmann and finite difference simulations of steady viscous flows[END_REF], achievable error [START_REF] Marié | Comparison between lattice Boltzmann method and Navier-Stokes high order schemes for computational aeroacoustics[END_REF], and runtimes [START_REF] Wichmann | A runtime based comparison of highly tuned lattice Boltzmann and finite difference solvers[END_REF]. However, there still is a lack of fair one-to-one comparisons. Indeed, most runtime-based results were obtained with two different solver developed independently and having different levels of optimisation. In addition, the numerical properties of the lattice Boltzmann method are highly dependent on the selected collision operator [START_REF] Wissocq | Linear stability and isotropy properties of athermal regularized lattice Boltzmann methods[END_REF][START_REF] Jacob | A new hybrid recursive regularised Bhatnagar-Gross-Krook collision model for lattice Boltzmann method-based large eddy simulation[END_REF] such that the conclusions of [START_REF] Marié | Comparison between lattice Boltzmann method and Navier-Stokes high order schemes for computational aeroacoustics[END_REF], only considering the BGK model, have to be tempered.

SCOPE OF THIS CONTRIBUTION

This work aims at rigorously comparing a lattice Boltzmann solver with an LES-type finite-volume Navier-Stokes solver.

The comparison is performed using ONERA's Cassiopée/Fast CFD environment implementing high-performance flow solvers which rely on the same code architecture and optimisation layers (see Figure 1).

MEANS AND METHOD OF COMPARISON

Firstly, the lattice Boltzmann method is compared to traditional finite-type Navier-Stokes schemes through von Neu- mann analyses. The latter consist in a linearisation of the corresponding algorithm about a mean flow and allow to investigate the behavior of linear waves in terms of propagation and dissipation. To do so, the von Neumann analysis introduced in [START_REF] Marié | Comparison between lattice Boltzmann method and Navier-Stokes high order schemes for computational aeroacoustics[END_REF] is extended by taking into account regularised LB collision models representative of those used for industrial-levels computations. Moreover, recent advances in LB linear stability analyses [START_REF] Wissocq | Linear stability and isotropy properties of athermal regularized lattice Boltzmann methods[END_REF] set the path towards two-dimensionnal wavenumber plane studies. By applying this idea to NS schemes, isotopy defects are highlighted for both numerical methods as shown on Figure 2. These defects are attributed to the coupling between spatial and temporal discretisations.

The results obtained by means of the von Neumann analyses are then validated through numerical test cases. The computation of monochromatic acoustic and shear plane waves gives an estimate of the number of points per wavelength required by each method to reach a certain error target. In addition, test cases representative of canonical aerodynamic problems such as a vortex convection (see Figure 3 for a qualitative comparison) and a 3D Taylor Green Vortex are considered. The influence of the LB collision model and NS spatial and time-stepping schemes are thoroughly discussed throughout the entire validation process. Finally, the CPU performance of both solvers is studied. The Roofline model [START_REF] Williams | Roofline: an insightful visual performance model for multicore architectures[END_REF], reformulated in "cell update" units, is applied to the lattice Boltzmann and finite-volume Navier-Stokes algorithms. Estimates about the maximum attainable performance are obtained and the main bottlenecks of the core loop of both solvers are evidenced.

Single-node scaling is performed and the measured performances are confronted to the Roofline model estimates. A "time to solution" metric is also introduced in order to fairly compare the LB and NS methods. It is shown that, in contrast to LB solvers, the "time to solution" of NS schemes does not only depend on the number of points per wavelength but also on the CFL number.

The results of this extended comparison exhibit that a fluid cell update is about two to three times faster with the lattice Boltzmann method w.r.t the finite-volume Navier-Stokes solver (see Figure 4). Regardless of the collision operator, the LB solver is especially suited for acoustic applications, offering speedups up to 10 compared to an LES-type NS solver.

On more "realistic" test cases such as a vortex convection or a 3D Taylor Green vortex, it is demonstrated that good qualitative results can be obtained in competitive runtimes with lattice Boltzmann methods. The latter perform outstandingly well for very low resolutions. However, for highly accurate results measured through L 2 or L ∞ norms, the finite-volume Navier-Stokes method outperforms the lattice Boltzmann solver in terms of "time to solution".

FastS

FastLBM BGK FastLBM HRR

1 Figure 1 :

 11 Figure 1: ONERA's Cassiopée/Fast CFD environment used for the comparison between the lattice Boltzmann and Navier-Stokes methods.

Figure 2 :Figure 3 :

 23 Figure 2: Dissipation error on the acoustic mode computed through the von Neumann analysis in a fluid medium at rest. Left : lattice Boltzmann BGK. Right: Navier-Stokes with 6thorder centered optimised spatial scheme.

Figure 4 :

 4 Figure 4: CPU time per cell per iteration for the FV-NS solver on structured cartesian grids and for the LBM with BGK HRR [7] collision operators.


Julien Hauret

Thomas Joubaud

Véronique Zimpfer

Éric Bavu

EBEN: EXTREME BANDWIDTH EXTENSION NETWORK APPLIED TO SPEECH SIGNALS CAPTURED WITH NOISE-RESILIENT BODY-CONDUCTION MICROPHONES

Keywords: Speech enhancement, PQMF-banks, Bandwidth extension, Frugal AI, Signal Processing

In this paper, we present Extreme Bandwidth Extension Network (EBEN), a Generative Adversarial network (GAN) that enhances audio measured with body-conduction microphones. This type of capture equipment suppresses ambient noise at the expense of speech bandwidth, thereby requiring signal enhancement techniques to recover the wideband speech signal. EBEN leverages a multiband decomposition of the raw captured speech to decrease the data time-domain dimensions, and give better control over the full-band signal. This multiband representation is fed to a U-Net-like model, which adopts a combination of feature and adversarial losses to recover an enhanced audio signal. We also benefit from this original representation in the proposed discriminator architecture. Our approach can achieve state-of-the-art results with a lightweight generator and real-time compatible operation.

INTRODUCTION

Speech capture for radio communications is traditionally performed using microphones located near the speaker's lips. However, this sound capture is sensitive to ambient noise, which reduces the intelligibility of communications in high noise levels such as in industry or on the battlefield. Under extreme conditions, even differential microphones are unable to get rid of high-level surrounding noise. Unconventional voice pickup systems such as bone conduction transducers, laryngophones or in-ear microphones integrated into hearing protections have great potential in many applications. These systems have higher impedance that is matched only by tissues and bones vibrations contrary to air molecules', making noise pollution almost imperceptible within captured speech [START_REF] Jeffrey C Bos | Speech input hardware investigation for future dismounted soldier computer systems[END_REF][START_REF] Acker-Mills | Speech intelligibility with acoustic and contact microphones[END_REF]. Yet, further research is needed to optimize the effective bandwidth of the captured speech signal as mid and high frequencies are missing due to the intrinsic low-pass characteristic of the biological pathway.

Since the desirable system is a two-way communication device, this entails real-time execution constraints, i.e. a short processing time (≤ 20 ms) to be indistinguishable to the hu-man ear. Moreover, edge computations are required to guarantee low latency, which in turn necessitates lightweight architectures. These considerations also match frugal AI requirements. Finally, the developed model should be robust to gender, accent, and speech loudness.

To perform this audio super-resolution task, we opt for deep learning techniques since classical signal processing source-filter approaches [START_REF] Iser | Bandwidth extension of speech signals[END_REF] have limited capabilities when the information has completely disappeared along a given frequency interval. Indeed, neural networks' ability to extract relevant features for the downstream task allows matching high and low frequency contents. Therefore, human processing should be minimal to let the network build its own representation, and could benefit from raw waveform inputs instead of spectrogram, mel-spectrogram [START_REF] Davis | Comparison of parametric representations for monosyllabic word recognition in continuously spoken sentences[END_REF] or MFCC [START_REF] Bruce | The quefrency alanysis of time series for echoes; cepstrum, pseudo-autocovariance, cross-cepstrum and saphe cracking[END_REF]. This trend is endorsed by several works [START_REF] Baevski | wav2vec 2.0: A framework for self-supervised learning of speech representations[END_REF][START_REF] Franc ¸ois G Germain | Speech denoising with deep feature losses[END_REF][START_REF] Dai | Very deep convolutional neural networks for raw waveforms[END_REF] for various audio tasks. The use of raw audio can also be combined with multiband processing to speed up inference as in RAVE [START_REF] Caillon | Rave: A variational autoencoder for fast and high-quality neural audio synthesis[END_REF]. To pursue the objective of fast inference, a fully convolutional architecture has been preferred in [START_REF] Van Den Oord | Wavenet: A generative model for raw audio[END_REF][START_REF] Volodymyr Kuleshov | Audio super-resolution using neural nets[END_REF], eventually U-Net-like for audio-to-audio tasks [START_REF] Stoller | Wave-unet: A multi-scale neural network for end-to-end audio source separation[END_REF][START_REF] Bosca | Dilated u-net based approach for multichannel speech enhancement from first-order ambisonics recordings[END_REF]. In addition, a simple reconstruction loss may be insufficient for conditional generation, producing unrealistic samples. As shown in [START_REF] Kumar | Melgan: Generative adversarial networks for conditional waveform synthesis[END_REF][START_REF] Kim | Bandwidth extension on raw audio via generative adversarial networks[END_REF][START_REF] Kong | Hifi-gan: Generative adversarial networks for efficient and high fidelity speech synthesis[END_REF], adversarial networks [START_REF] Goodfellow | Generative adversarial networks[END_REF] can significantly improve the naturalness of produced sound.

Based on the above observations, we developed EBEN, a new deep learning model, inspired by Seanet [START_REF] Tagliasacchi | Seanet: A multi-modal speech enhancement network[END_REF] to infer mid and high frequencies from speech containing only low frequencies. As in the original paper, we use a generator that maps the degraded speech signal to an enhanced version. The generator is optimized to produce samples which are close to the reference while maintaining a certain degree of naturalness at different time scales. A multiband decomposition using Pseudo-Quadrature Mirror Filters (PQMF) [START_REF] Truong Q Nguyen | Near-perfect-reconstruction pseudo-qmf banks[END_REF] is applied to reduce the temporal dimension of input features and to focus the signal's discrimination solely on high frequency bands. We therefore share a common goal with [START_REF] Li | Real-time speech frequency bandwidth extension[END_REF], but differ in methodology and addressed degradations.

We used recordings 1 from a non conventional in-ear pro-totype in order to study the signal degradation. Focusing on capture-induced degradation of a specific device does not penalize the generality of our approach. This family of sensors consistently degrades speech in the same way, acting as a low-pass filter. Variations mostly occur in terms of cut-off frequency, attenuation, and lack of coherence at specific frequencies. Thus, to address any other system, it would be enough to have a matching dataset. The few minutes of recordings at our disposal being insufficient, we trained our model and several baselines [START_REF] Volodymyr Kuleshov | Audio super-resolution using neural nets[END_REF][START_REF] Kong | Hifi-gan: Generative adversarial networks for efficient and high fidelity speech synthesis[END_REF][START_REF] Tagliasacchi | Seanet: A multi-modal speech enhancement network[END_REF][START_REF] Li | Real-time speech frequency bandwidth extension[END_REF] with the French version of the Librispeech dataset [START_REF] Vineel Pratap | Mls: A large-scale multilingual dataset for speech research[END_REF] with simulated degradations, hoping to later release a publicly available dataset of speech capture with noise-resilient body-conduction microphones.

METHODS

Degradation estimation

The selected equipment is an early prototype of in-ear transducer [START_REF]BIONEAR outstanding hearing for 4.0 professionals[END_REF] developed by ISL and Cotral Lab. This device takes advantage of the speaker's hearing protection by being placed inside a custom-molded earplug, which increases communication capabilities in challenging and noisy environments. The captured signal mainly contains speech with no environmental noise. However, the acoustic path between the mouth and the transducers acts as a low pass filter: practically no relevant speech signal is picked up above a threshold frequency. This phenomenon can be further influenced by the occlusion effect due to the fitting of the individual protectors and some complex interactions with tissues. To evaluate this transfer function, the experimental protocol consists in capturing speech simultaneously with the in-ear transducer and a regular microphone placed in front of the speaker's mouth under noise-free conditions. Since speech signals are not stationary, several short-window estimates were respectively used to produce an estimated degradation -under the first approximation of a linear transfer function -shown in Fig. 1 The joint analysis of plots in Fig. 1 shows that speech frequency content is only captured in a range below 2 kHz: the coherence function is close to zero above this frequency, and the gain of the transfer function is very low. This indi-cates that the in-ear microphone exhibits a very high attenuation at mid and high frequencies. Interestingly, at very low frequencies, the coherence function also indicates a lack of correlation between the two signals, since in-ear transducers also pick up physiological sounds produced by swallowing or blood flow. Finally, two anti-resonances are observed at 900 Hz and 1700 Hz, corresponding to vibration nodes of the occluded inner ear and propagation in bones and tissues.

Pseudo Quadrature Mirror Filter formalism

The Quadrature Mirror Filter (QMF) banks, introduced in [START_REF] Rothweiler | Polyphase quadrature filters-a new subband coding technique[END_REF], are a set of analysis filters {H i } i∈[1,M ] used to decompose a signal into several non-overlapping channels of same bandwidth, and synthesis filters {G i } i∈[1,M ] used to recompose the signal afterward. Those filters are obtained from the same lowpass prototype filter. A typical frequency response for a M-band PQMF bank is given in Fig. 2. Fig. 3 shows the entire pipeline. The reconstruction is exact if

{H i } i∈[1,M ] and {G i } i∈[1,M ] have an infinite support.
In practice, a convolution kernel of 8M is enough to produce a near perfect pseudo reconstruction x with well-chosen 2 filters [START_REF] Truong Q Nguyen | Near-perfect-reconstruction pseudo-qmf banks[END_REF]. . . .

0 ω . . . |H 1 (e jω )| |H 2 (e jω )| |H M (e jω )| -π M | π 2M | π M | 2π M | (M -1)π M | (M +1)π M | π |
H i (z)
. . .

H M (z) ↓ M . . . ↓ M . . . ↓ M ↑ M . . . ↑ M . . . ↑ M G 1 (z)
. . .

G i (z)
. . .

G M (z) + x

Fig. 3. PQMF Analysis and Synthesis : block-diagram

When used in a subband coding context, the PQMF analysis filter's outputs are decimated (downsampled) by a factor M . This can speed up inference because the different bands are modeled as conditionally independent. The PQMF analysis can also be seen as an downsampling operator, allowing to generate channels with considerably reduced redundancy, leading to a reduction in computational complexity. Along with EBEN source code, we provide a modern and efficient implementation of the PQMF analysis and synthesis with native Pytorch functions, using strided convolutions and strided transposed convolutions only.

Model architecture

Unlike the Seanet generator, where the very first layer is a plain convolution used to process the audio at the original 16kHz sampling rate, we propose for EBEN to encapsulate a U-Net-like generator between a PQMF analysis layer and a PQMF synthesis layer. This allows to reduce the memory footprint of the model by reducing the first embeddings samplerate by a factor of M. It also makes possible to keep only subbands having voice content to feed the U-Net first convolution. Moreover, the number of encoder/decoder blocks is reduced to meet the constraints of real-time applications.

EBEN's discriminator also differs from the Seanet approach, as we directly exploit the PQMF subbands as multiple discriminator's inputs, without recombining nor upsampling the reconstructed subband signals. As shown in Fig 4, we adopt a multiscale ensemble discriminator approach, inspired by the work of Kumar et al. in [START_REF] Kumar | Melgan: Generative adversarial networks for conditional waveform synthesis[END_REF], whose inputs are the upper bands of the PQMF decomposition. This allows the ensemble of discriminators to analyze the generated subband signals at different time scales, and helps the generator to be trained to generate high quality samples despite the fact that each discriminator is relatively simple. The subband discriminators {D k } k∈ [START_REF] Jeffrey C Bos | Speech input hardware investigation for future dismounted soldier computer systems[END_REF][START_REF] Acker-Mills | Speech intelligibility with acoustic and contact microphones[END_REF][START_REF] Iser | Bandwidth extension of speech signals[END_REF] exhibit similar receptive fields to the original Seanet. As shown in Fig. 4, the full scale MelGAN discriminator was however kept from the Seanet approach, in order to ensure coherence between bands.

Loss functions

Discriminators are trained with a classical hinge loss. In L D , and L G , G represents the generator and D (l) k,t represents the layer l of the discriminator (among L k layers) of scale k (among K scales) at time t. F k,l and T k,l are the number of features and temporal length for given indices. x is the in-ear signal while y is the reference.

L D = E y   1 K k∈[0,3] 1 T k,L k t max(0, 1 -D k,t (y))   + E x   1 K k∈[0,3] 1 T k,L k t max(0, 1 + D k,t (G(x)))  
For the generator, we adopted a loss function composed of a generative part L G adv and a reconstructive part L G rec , balanced by λ :

L G = L G adv + λL G rec . L adv G = E x   1 K k∈[0,3] 1 T k,L k t max(0, 1 -D k,t (G(x)))   L rec G = E x     1 K k∈[0,3] l∈[1,L k [ 1 T k,l F k,l t D (l) k,t (y) -D (l) k,t (G(x)) L1    
This combination allows to generate audio samples as close as possible to the reference signal thanks to L rec G , while remaining creative at high frequencies when no information is available in the degraded signal (especially for fricatives) thanks to L adv G . Note that L rec G does not operate directly in the time domain but in discriminators domain to focus on the signal semantic (feature matching).

EXPERIMENTS

A simulated degradation (described in Sec. 3.1) is performed on the French Librispeech [START_REF] Vineel Pratap | Mls: A large-scale multilingual dataset for speech research[END_REF] dataset. Different models [START_REF] Volodymyr Kuleshov | Audio super-resolution using neural nets[END_REF][START_REF] Kong | Hifi-gan: Generative adversarial networks for efficient and high fidelity speech synthesis[END_REF][START_REF] Tagliasacchi | Seanet: A multi-modal speech enhancement network[END_REF][START_REF] Li | Real-time speech frequency bandwidth extension[END_REF] and the EBEN approach have been trained on this imitated in-ear dataset during 2 days on a single RTX 2080 Ti GPU. Each model is evaluated objectively (Sec. 3.2) and subjectively (Sec. 3.3). No parameter tuning nor early stopping was performed.

Simulation of the dataset

The simulated degradation is based on an autoregressive moving-average model, using a 2 nd order low-pass filter with a cutoff frequency of 600 Hz and unitary Q-factor that is applied using a filtfilt procedure to ensure zero phase shift. The superposition of the simulated and estimated degradation filters are represented on Fig. 1 (a). A Gaussian white noise with a power 23 dB below the selected signal is also added. This simplistic degradation still ensures a wide application field for developed algorithms and the ability to focus on the bandwidth extension issue. Future works will introduce variable filters with anti-resonance frequencies and realistic physiological noise.

Objective evaluation

To evaluate the model performances, Tab. 1 highlights several objective metrics: Perceptual Evaluation of Speech Quality (PESQ) [START_REF] Rix | Perceptual evaluation of speech quality (pesq)-a new method for speech quality assessment of telephone networks and codecs[END_REF], Scale-Invariant Signal-to-Distortion Ratio (SI-SDR) [START_REF] Le Roux | Sdr-half-baked or well done?[END_REF] and Short-Time Objective Intelligibility (STOI) [START_REF] Cees H Taal | A short-time objective intelligibility measure for time-frequency weighted noisy speech[END_REF] on test set. Speech enhancement being a one-tomany problem, these results should be analyzed cautiously. Indeed, a plausible signal with perfect intelligibility but still different from reference would be misjudged by the metrics. Note that these metrics are intrusive, since they require a groundtruth audio. Generally speaking, speech quality assessment is lacking non subjective and non comparative evaluation metrics. Works like Noresqa [START_REF] Manocha | Noresqa: A framework for speech quality assessment using non-matching references[END_REF] attempted to introduce such non intrusive metrics, but were inefficient for our specific degradation. We also report on Tab. 1 the number of parameters for each model, showing that EBEN is among the lightest. Time latency and computational load are presented on the project website 1.

Subjective evaluation

To visually assess and compare the results of approaches, Fig. 5 shows some spectrograms obtained from the testing set. It can be observed that a purely reconstructive approach [START_REF] Volodymyr Kuleshov | Audio super-resolution using neural nets[END_REF] is not sufficient to produce high frequencies. Indeed, when low frequency information is insufficient, the model predicts the mean of speech signals which is zero. Among gener-ative approaches, our method reconstructs a fair amount of formants and minimizes artifacts. We also conducted a subjective evaluation of the different methods using the MUltiple Stimuli with Hidden Reference and Anchor [START_REF] Series | Method for the subjective assessment of intermediate quality level of audio systems[END_REF] (MUSHRA) methodology on the GoListen platform [START_REF] Barry | Go listen: an end-to-end online listening test platform[END_REF]. Obtained results are also given on Tab. 1. MUSHRA-U is about ease of understanding while the MUSHRA-Q is about audio quality. Our approach is ranked first ex-aequo with Seanet for both aspects.

DISCUSSION AND FUTURE WORK

EBEN is a realtime-compatible network architecture to address the problem of bandwidth extension of speech signals captured with body-conduction microphones. The proposed multiband approach offers several benefits, including reduced parameters and the ability to select the bands to operate on with a GAN approach. Developing a lightweight causal architecture able to capture long-range dependencies to disambiguate some phonetical content could help to further improve speech reconstructions for severe degradations.

  (a) and the coherence function on Fig. 1(b).

Fig. 1 .

 1 Fig. 1. Degradation analysis of the in-ear transducer

Fig. 2 .

 2 Fig. 2. Frequency response of a PQMF filter bank

:

  Generator weights trained with LG : Discriminators weights trained with LD : Block described on Figure3: Block described on Figure3

Fig. 4 .

 4 Fig. 4. Overall architecture represented for M = 4, one band with voice content fed to generator, others to PQMF discriminators

Fig. 5 .

 5 Fig. 5. Spectrograms of various bandwidth extension models sandwiched by the simulated in-ear and the reference signals.

Table 1 .

 1 Comparing models with: PESQ/SI-SDR/STOI on test set -MUSHRA-U (88 participants) and MUSHRA-Q (82 participants) scores -number of parameters. Format is median (IQR). Significantly best values (acceptance=0.05) are in bold.

	Speech	Metrics PESQ	SI-SDR	STOI	MUSHRA-U MUSHRA-Q Gen params Dis params
	Simulated In-ear Audio U-net [11] Hifi-GAN v3[16]	2.42 (0.34) 8.4 (3.7) 2.24 (0.49) 11.9 (3.7) 1.32 (0.16) -25.1 (11.4) 0.78 (0.04) 40 (23) 0.83 (0.05) 51 (29) 0.87 (0.04) 60 (26)	24 (18) 33 (18) 36 (18)	∅ 71.0 M 1.5 M	∅ ∅ 70.7 M
	Seanet [18]	1.92 (0.48) 11.1 (3.0)	0.89 (0.04) 73 (13)	78 (12)	8.3 M	56.6 M
	Strm-Seanet [20]	2.01 (0.46) 11.2 (3.6)	0.89 (0.04) 66 (20)	61 (14)	0.7 M	56.6 M
	EBEN (ours)	2.08 (0.45) 10.9 (3.3)	0.89 (0.04) 73 (14)	76 (14)	1.9 M	27.8 M

available to listen at https://jhauret.github.io/eben alongside source code, hyparameters and model performances

Acknowledgements: This work has been partially funded by the French National Research Agency under the ANR Grant No. ANR-20-THIA-0002. This work was also granted access to the HPC/AI resources of [CINES / IDRIS / TGCC] under the allocation 2022-AD011013469 made by GENCI.


Isabelle Lampre

Jean-Louis Marignier

Malaknaz Mirdamadi-Esfahani

Pascal Pernot

Pierre Archirel

Mehran Mostafavi

Oxidation of Bromide Ions by Hydroxyl Radicals: Spectral Characterization of the Intermediate BrOH •

Keywords: Pulse radiolysis, absorption spectrum, global analysis, quantum chemical calculations

The reaction of • OH with Br -has been re-investigated by picosecond pulse radiolysis combined with streak camera absorption detection and the obtained spectro-kinetics data have been globally analyzed using Bayesian data analysis. For the first time, the absorption spectrum of the intermediate species BrOH •-has been determined. This species absorbs in the same spectral domain as Br2 •-: the band maximum is roughly at the same wavelength (max = 352 nm instead of 354 nm) but the extinction coefficient is smaller (max = 7800  400 dm 3 mol -1 cm -1 compared with 9600  300 dm 3 mol -1 cm -1 ) and the band is broader (88 nm versus 76 nm). Quantum chemical calculations have also been performed and corroborate the experimental results. In contrast to Br2 •-, the existence of several water-BrOH •-configurations leading to different transition energies may account for the broadening of the absorption spectrum in addition to the higher number of degrees of freedom.

INTRODUCTION

The oxidation of bromide ions, Br -, and the subsequent formation of Br2 •-and Br3 -in aqueous solutions has been the subject of many radiolysis studies. [START_REF] Rafi | Radiolysis of aerated solutions of potasium bromide[END_REF][START_REF] Sutton | Radical yields and kinetics in pulse radiolysis of potassium bromide[END_REF][START_REF] Matheson | The pulse radiolysis of deaerated aqueous bromide solutions[END_REF][START_REF] Zehavi | Pulse radiolytic investigation of Oaqradical ions[END_REF][START_REF] Zehavi | The oxidation of aqueous bromide ions by hydroxyl radicals. A pulse radiolytic investigation[END_REF][START_REF] Behar | Pulse radiolysis studies on Brin aqueous solution: the mechanism of Br2formation[END_REF][START_REF] Treinin | Charge transfer spectra of halogen atoms in water. Correlation of the electronic transition energies of iodine, bromine, chlorine, hydroxyl, and hydrogen radicals with their electron affinities[END_REF][START_REF] Mamou | On the oxidation of aqueous Brby OH radicals, studied by pulse radiolysis[END_REF][START_REF] D'angelantonio | A re-examination of the decay kinetics of pulse radiolytically generated Br2radicals in aqueous solution[END_REF][START_REF] Hug | Multiple time scales in pulse radiolysis. Application to bromide solutions and dipeptides[END_REF][START_REF] Baldacchino | Hydroxyl radical yields in the tracks of high energy 13 C 6+ and 36 Ar 18+ ions in liquid water[END_REF][START_REF] Mirdamadi-Esfahani | Radiolytic formation of tribromine ion Br3in aqueous solutions, a system for steady-state dosimetry[END_REF][START_REF] Balcerzyk | Direct and indirect radiolytic effects in highly concentrated aqueous solutions of bromide[END_REF][START_REF] Lin | Temperature dependence absorption spectra of Br -, Br2°-, and Br3in aqueous solutions[END_REF] The dibromine radical anion (Br2 •-) is a strong oxidising radical characterized by a broad optical absorption band centred at 360 nm with an extinction coefficient, max(Br2 •-), of 9900 ± 600 dm 3 mol -1 cm -1 , [START_REF] Hug | Optical spectra of nonmetallic inorganic transient species in aqueous solution[END_REF] while the tribromine ion (Br3 -) is a stable species which has an intense but narrow absorption spectrum located at 266 nm with , max(Br3 -) = 40900 ± 400 dm 3 mol -1 cm -1 . [START_REF] Mirdamadi-Esfahani | Radiolytic formation of tribromine ion Br3in aqueous solutions, a system for steady-state dosimetry[END_REF][START_REF] Wang | Equilibrium, kinetic, and UV-spectral characteristics of aqueous bromine chloride, bromine, and chlorine species[END_REF] It has been established that the oxidation of Br -by the hydroxyl radical ( • OH) is not a simple electron transfer reaction but involves the intermediate adduct BrOH •-. The latter may react with the hydronium cation (H3O + ), dissociate to produce the bromine atom (Br • ) as well as react with another Br -and produce Br2 •-. The oxidation mechanism is in fact quite complex with reversible reactions:

• OH + Br - BrOH •- k1 = (1.06 ± 0.08)  10 10 dm 3 mol -1 s -1 5 (R1)

k -1 = (3.3 ± 0.4)  10 7 s -1 5

BrOH •- Br • + OH - k2 = (4.2 ± 0.6)  10 6 s -1 5 (R2) k -2 = 1.3  10 10 dm 3 mol -1 s - 1 17, 18 BrOH •-+ Br - Br2 •-+ OH - k3 = (1.9 ± 0.3)  10 8 dm 3 mol -1 s -1 5 (R3) k -3 = (2.7 ± 0.5)  10 6 dm 3 mol -1 s -1 8

BrOH •-+ H3O + Br • (+ 2H2O) k4 = (4.4 ± 0.8)  10 10 dm 3 mol -1 s -11 5 (R4) k -4 = 1.36 s - 1 17 Br • + Br - Br2 •- k5 = (1.2 ± 0.1)  10 10 dm 3 mol -1 s -1 19 (R5) k -5 = 1.9  10 4 s - 1 19 Br2 •-+ Br2 •- Br3 -+ Br - k6 = (1.9 ± 0.1)  10 9 dm 3 mol -1 s -1 9 (R6)

Br2 + Br - Br3 - K7 = 16.1 ± 0.3 dm 3 mol -1 [START_REF] Wang | Equilibrium, kinetic, and UV-spectral characteristics of aqueous bromine chloride, bromine, and chlorine species[END_REF] (R7)

The intermediate BrOH •-was first suggested by Matheson, et al. [START_REF] Matheson | The pulse radiolysis of deaerated aqueous bromide solutions[END_REF] and then supported by works of Behar [START_REF] Behar | Pulse radiolysis studies on Brin aqueous solution: the mechanism of Br2formation[END_REF] and Zehavi and Rabani. [START_REF] Zehavi | Pulse radiolytic investigation of Oaqradical ions[END_REF][START_REF] Zehavi | The oxidation of aqueous bromide ions by hydroxyl radicals. A pulse radiolytic investigation[END_REF] While it was identified in irradiated frozen aqueous solutions of alkali metal halides by electron spin resonance spectroscopy, [START_REF] Marov | Unstable intermediates. Part LXXXII. Electron spin resonance spectra of the species Br2 -, I2 -, BrOH -, and IOHin γ-irradiated frozen aqueous solutions of alkali-metal halides[END_REF] its optical characterization was not obvious and it was reported that BrOH •-either does not absorb [START_REF] Behar | Pulse radiolysis studies on Brin aqueous solution: the mechanism of Br2formation[END_REF] or has an absorption similar to Br2 •-. [START_REF] Zehavi | The oxidation of aqueous bromide ions by hydroxyl radicals. A pulse radiolytic investigation[END_REF] In the sixties, there were also some disagreements on the values of the rate constant of the reaction between • OH and Br -, mainly due to pH sensitivity of the system. Sutton et al. reported that, in contrast to the corresponding reaction with chloride ion, the reaction between • OH and Br -was exothermic and occurs rapidly even in neutral solution (k1  10 9 dm 3 mol -1 s -1 ). [START_REF] Sutton | Radical yields and kinetics in pulse radiolysis of potassium bromide[END_REF] The pulse radiolysis of deaerated aqueous bromide solutions by Matheson at al. yielded the value k1 = (1.2  0.15)  10 9 dm 3 mol -1 s -1 . [START_REF] Matheson | The pulse radiolysis of deaerated aqueous bromide solutions[END_REF] Then, Zehavi and Rabani elucidated the mechanism of bromide oxidation by • OH radicals and determined a tenfold higher value for k1. [START_REF] Zehavi | The oxidation of aqueous bromide ions by hydroxyl radicals. A pulse radiolytic investigation[END_REF] This value given above corresponds to the value now used as a reference. [START_REF] Buxton | Critical review of rate constant of hydrated electrons, hydrogen atoms and hydroxyl radicals in aqueous solution[END_REF] Zehavi and Rababi attempted to measure the absorption spectrum of BrOH •-. They found that the absorption of the intermediate BrOH •-is quite similar to that of Br2 •-; the spectrum of BrOH •-exhibits a band around 360 nm broader than that of Br2 •-and with a lower extinction coefficient. [START_REF] Zehavi | The oxidation of aqueous bromide ions by hydroxyl radicals. A pulse radiolytic investigation[END_REF] Taking into account the absorbance of BrOH •-, Mamou et al. removed some discrepancies in the kinetics data. [START_REF] Mamou | On the oxidation of aqueous Brby OH radicals, studied by pulse radiolysis[END_REF] Even if it is now admitted that BrOH •-is an absorbing species, [START_REF] Hug | Multiple time scales in pulse radiolysis. Application to bromide solutions and dipeptides[END_REF] to our knowledge its absorption spectrum has not yet been characterized. In this paper, we present a pulse radiolysis study of sodium bromide solution.

Thanks to a new detection set-up based on a CCD camera with a high resolution and a global Bayesian data analysis, we were able to distinguish between BrOH •-and Br2 with success in the past years for the analysis of spectrokinetic data. [START_REF] Caer | Successive reactions of iron carbonyl cations with dimethyl ether: direct cleavage versus rearrangement[END_REF][START_REF] Renou | Solvated electron pairing with earth alkaline metals in THF. 1. Formation and structure of the pair with divalent magnesium[END_REF][START_REF] Renou | Solvated electron pairing with earth alkaline metals in THF. 2. Reactivity of the (Mg II , es -) pair with aromatic and halogenated hydrocarbon compounds[END_REF][START_REF] Mozziconacci | Superoxide radical anions protect enkephalin from oxidation if the amine group is blocked[END_REF][START_REF] Soroushian | Solvation dynamics of the electron produced by two-photon ionization of liquid polyols. I. Ethylene glycol[END_REF][START_REF] Bonin | Solvation dynamics of electron produced by two-photon ionization of liquid polyols. II. Propanediols[END_REF][START_REF] Bonin | Solvation dynamics of electron produced by two-photon ionization of liquid polyols. III. Glycerol[END_REF][START_REF] Schmidhammer | Distance dependence of the reaction rate for the reduction of metal cations by solvated electrons: a picosecond pulse radiolysis study[END_REF][START_REF] El Omar | Time-Dependent Radiolytic Yield of OH• Radical Studied by Picosecond Pulse Radiolysis[END_REF] It has proved to be an essential tool to tackle parametric identification problems, which are omnipresent in the kinetic modeling of time-resolved spectra. Quantum calculations have also been performed

for both species to provide some insights on the electronic transitions responsible of the absorption.

EXPERIMENTAL AND COMPUTATIONAL SECTION

Materials. The aqueous solutions were prepared using ultra-pure water from a Millipore system. The chemicals, sodium bromide NaBr (purity >99%) and acetone, were obtained from Sigma-Aldrich and used as received without further purification. The solutions were saturated with dinitrogen or argon (N2, Ar, purity >99.995% from Air Liquide) by bubbling before and during experiments. The solutions with a natural pH around 5.5 were stable at room temperature under room light. All solutions were irradiated at room temperature (~20°C).

Pulse radiolysis measurements.

The experiments were carried out on the picosecond laser-triggered electron accelerator ELYSE at University Paris-Sud (Orsay) coupled with an absorption spectroscopic detection system. [START_REF] Marignier | Time-resolved spectroscopy at picisecond laser-triggered electron accelerator ELYSE[END_REF][START_REF] Belloni | Ultrafast pulse radiolysis methods[END_REF] Electron pulses with 7.9 MeV energy, ~6 nC charge and 15 ps duration were delivered at a repetition rate of 2 Hz. The dose deposited in water was around 50 Gy in the irradiated volume (i.e. [eaq -]  2  10 -5 M). The studied sample was contained in a 10  10 mm irradiation quartz cell. A close circulation system from a 100 mL N2-purged stock solution was used to renew the sample between each pulse (peristaltic pump, flow rate 80 mL/min). Absorption measurements were performed using the white light beam of a homemade Xenon flash lamp. [START_REF] Herren | Light flash generatoir, absorption spectrometer including such a generator and method for generating light flashes[END_REF] The light was focused through the sample collinearly with the electron beam and then directed onto the detection set-up which was composed of a spectrograph (Chromex 250IS) and a high dynamic range streak camera (Hamamatsu C7700-01). For this study, a 150 grooves/mm and 300 nm blaze grating and 200 µm slits were used and 20 ns, 50 ns or 500 ns sweep time/full screen were performed. For each flash, an image (1024 × 1344 pixels) resolved in time and wavelength (340 nm full screen) was acquired but to get a good signal to noise ratio series of 700 images were averaged in a unique image. Then, the time-resolved absorbance of the sample was calculated using average images obtained with and without the electron pulses. The full spectra from 300 to 590 nm were obtained by two series of absorption measurements using two different optical filters (UG 5 and GG325) to optimize the light intensity on a specific spectral domain (290 to 420 nm and 360 to 590 nm, respectively). The spectral overlap between 360 and 420 nm allows us to check the good stability and reproducibility of the irradiation measurements.

Bayesian data analysis.

A general introduction on Bayesian data analysis can be found in Gregory's book, [START_REF] Gregory | Bayesian logical data analysis for the physical sciences: a comparative approach with Mathematica support[END_REF] and a more focused treatment on spectrokinetic data in the paper written by Ruckebusch and co-workers. [START_REF] Ruckebusch | Comprehensive data analysis of femtosecond transient absorption spectra: a review[END_REF] A minimal overview is provided here.

Bayesian data analysis is based on the posterior probability density function (pdf)

p(θ|D,H), which is a Nθ-dimensional distribution over the values of a set of Nθ uncertain parameters θ, conditional to the values of the experimental data D and to an ensemble of hypotheses H. The posterior pdf can be built from available information through the Bayes theorem:

p(θ|D,H)  p(D|θ,H) × p(θ|H) (1)
The function p(D|θ,H) is called the likelihood; it describes the statistical model of measurement uncertainties, while the prior pdf p(θ|H) represents the state of knowledge on the parameters before analyzing the data. For the present study, the norm factor of the posterior pdf is not useful and has been left unspecified.

Technically, a search for the optimal parameter set, the so-called Maximum A Posteriori (MAP) parameters, is performed in order to assess the goodness-of-fit of the model and to provide a favorable starting point for the random walk (Markov Chain Monte Carlo, MCMC) through which a representative sample of the posterior pdf is generated by a Metropolis-Hastings algorithm. 36 Estimates of the parameters and their uncertainties are obtained from this sample.

In the present study, the experimental data images were downsized to a 70 × 70 spectrokinetics data matrix D with a final resolution of 3.4 ns and 2.7 nm. We used a hybrid spectrokinetic model M, where the kinetic traces are described by a parametric kinetic model and the spectra are treated non parametrically, as described by Ruckebusch et al. [START_REF] Ruckebusch | Comprehensive data analysis of femtosecond transient absorption spectra: a review[END_REF] The recovery of the spectra is affected by various sources of uncertainty: (i) data uncertainty (measurement noise, time and wavelength calibration), and (ii) uncertainty associated to the parameters of the spectrokinetic model and the model itself.

The first source of uncertainty is accounted for by a proper treatment of data noise by using a variance/covariance matrix in the likelihood function. In the present study, we assumed that the time and wavelength are known without random uncertainty. They might be affected by a systematic error without impact on the results of the present study. The data noise is heteroscedastic (not uniform) in wavelength for two reasons: composite image and camera sensitivity. Before downsizing the noise structure was analyzed in the time-asymptotic part of the image, where there is no/few signal evolution. For each wavelength channel, the standard deviation (corrected from a possible linear variation) was estimated over 200 time points of the raw data matrix (Supporting Information, blue dots in Figure S1). A wavelength-wise local linear regression (loess interpolation) of the noise amplitude was used as a proxy for the average noise amplitude used to calculate weighted residuals. In order to get a standard Gaussian distribution of the weighted residuals, we had to correct the noise amplitude by a multiplicative factor (1.4). This new noise level corresponds approximately to the wavelength-dependent upper bound of a symmetric 90 % confidence interval for the noise amplitude (Supporting Information, red curve in Figure S1). The likelihood function is expressed, up to its norm factor, as

( )   2 2 11 , M exp ( ) 2 kl kl lk l p D M     - -    D (2)
where the indices l and k cover the wavelength and time grid, respectively, and l represents the wavelength-dependent standard deviation of measurement noise.

For parametric uncertainty, we distinguish amongst internal parameters, int, which are directly related to the conditions of the current data (initial concentrations of reagents, initial time calibration...), and external parameters, ext, for which, in the case where the model is valid, we do not expect to gather information from the data. Initially, the rate constants are treated as external uncertain parameters, because it is not a priori obvious that there is enough information in the present data to get a reasonable inference on their values. A contrario, we include the absorption coefficient max(Br2 •-) into the internal or Optimized Parameters Set (OPS), because its value in the experiment could be affected by the calibration of the dose, for instance. In the course of the analysis, the OPS might be augmented by recruiting parameters of the external set, until residuals analysis enables to conclude to a reasonable fit of the data.

As the parameters in the OPS are uncorrelated in the present study, the prior pdf is simply the product of the prior pdfs of the individual parameters:

( ) ( )

MM i i pp  =  (3)

Monte Carlo Uncertainty Propagation (MCUP).

Bayesian inference in the OPS is conditional to the values of the parameters in the external set. As the latter are uncertain, we have to check their influence on the inferred values. Expliciting the partition of the parameters, the posterior pdf for the parameters of the OPS can be noted p(int| ext ,D,M), and the effect of the uncertainty in the external parameters obtained by Uncertainty Propagation (Markov Equation, see reference 37)

( ) ( ) ( ) ,M , ,M M int ext int ext ext p d p p      =  DD ( 4
)
where the design of p( ext |M) is similar to the prior pdf defined above.

Implementation of Equation 4 is commonly done by a Monte Carlo approach (noted MCUP thereafter), where a representative sample of the left hand side pdf is obtained by evaluating the posterior pdf for a representative sample of p( ext |M). As the posterior pdf is itself obtained by Markov Chain Monte Carlo sampling, this results in a double Monte Carlo method, which is very computer intensive. We used here an approximation evaluating the impact of p( ext |M) on the Maximum A Posteriori for the internal parameters  int MAP . This is often sufficient to appreciate the impact of the external parameters. An approximation of the total variance of the internal parameters, u 2 ( int ), due to the data and external parameters can be obtained as:

( ) ( ) 2 2 2 u ( ) u , u MAP ext int int int     =+ DD (5)
where ext  denotes the nominal value of the corresponding external parameters.

All calculations have been performed with the R language. 38 URL http://www.R-project.org/ #71 URL http://www.R-project.org/ #71

Quantum calculations for transition energies. To determine the electronic transitions of BrOH •-and Br2 •-in aqueous solution, the systems Br2 •-(H2O)n and BrOH •-(H2O)n, with n small were studied using a conventional TDDFT method on a set of configurations and modeling the solvent with a PCM reaction field in the SMD formalism. The SDD core pseudo-potentials and basis sets were used supplemented with polarization Gaussians on all atoms: one d on O atoms (exponent: 0.8) and Br atoms (0.3) and one p on H atoms (1.1). [START_REF] Fuentealba | A proper account of corepolarization with pseudopotentials: single valence-electron alkali compounds[END_REF] This polarized SDD basis set is noted pSDD. All calculations were carried out with the Gaussian 09 program 40 and Molpro ab initio program 41 packages.

RESULTS AND DISCUSSION

Pulse radiolysis. Radiolysis of neutral aqueous solutions mainly generates hydrated electrons (eaq -), hydroxyl radicals ( • OH) and hydrogen atom (H • ). • OH and H • absorb weakly far in the UV spectral domain [START_REF] Buxton | Critical review of rate constant of hydrated electrons, hydrogen atoms and hydroxyl radicals in aqueous solution[END_REF] and will not be detected above 300 nm, our spectral domain of interest. In contrast, eaq -presents a strong and very broad absorption band centred at 720 nm which overlaps the spectral domain of Br2 •-absorption. Indeed, the molar extinction coefficient of eaq -at 360 nm (360 nm(eaq -) = 1790 dm 3 mol -1 cm -1 ) is roughly one fifth of that of Br2 •-. In order to get rid of the eaq -contribution to the absorption signals, acetone was used to scavenge the hydrated electron as the formed alcohol radical, (CH3)2C • OH, hardly absorbs in the explored spectral domain ( < 500 dm 3 mol -1 cm -1 for  > 300 nm): [START_REF] Kasama | Photochemical reactions of triplet acetone with indole, purine and pyrimidine derivatives[END_REF][START_REF] Mills | Radiation chemistry of Na3IrCl6 solutions: catalysed H2 formation by radicals and postirradiation reduction of IrCl6 3by propanol-2[END_REF] eaq -+ (CH3)2CO (CH3)2C • O - k8 = 6.5  10 9 dm 3 mol -1 s -1 21 (R8) [START_REF] Laroff | Equilibrium and kinetics of the acid dissociation of several hydroxyalkyl radicals[END_REF] (R9)

(CH3)2C • OH (CH3)2C • O -+ H + pKa = 12
• OH can also react with acetone but the rate constant is two orders of magnitude lower than that of reaction R1 with Br -:

• OH + (CH3)2CO products k10 = 1.3  10 8 dm 3 mol -1 s -1 45 (R10)
The generated products do not absorb in the studied spectral domain. Indeed, pulse-radiolysis of Ar-purged aqueous solutions containing acetone alone shows only a weak absorption due to (CH3)2C • OH generated by R8-9 (Supporting Information, Figure S2).

It is to be noted that N2O-saturated solution (2.5  10 -2 M N2O) could have been used to convert eaq -into • OH: order rate constant for the disappearance of eaq -is found to be 6.7  10 8 s -1 . Taking into account the concentration of acetone, that corresponds to a bimolecular rate constant of 6.7  10 9 dm 3 mol -1 s -1 ; this value is in the range (from 5.6  10 9 dm 3 mol -1 s -1 to 8  10 9 dm 3 mol -1 s -1 ) of the reported values [START_REF] Barat | Effect of the dielectric constant on the reactivity of the solvated electron[END_REF][START_REF] Afanassiev | Effect of solvation energy on electron reaction rates in hydroxylic solvents[END_REF][START_REF] Philips | Radiation induced diffusion controlled reactions. A probe for enhanced solute diffusion in polysaccharide matrices[END_REF][START_REF] Idriss-Ali | Electron behavior in mixed solvents: optical spectra and reactivities in water/alkane diols[END_REF][START_REF] Maham | Effect of solvent structure on the electron reactivity: 1propanol/water mixtures[END_REF][START_REF] Lai | Solvent effects on the reactivity of solvated electrons with organic solutes in methanol/water and ethanol/water mixed solvents[END_REF] and in good agreement with the average selected value (6.5  10 9 dm 3 mol -1 s -1 ) [START_REF] Buxton | Critical review of rate constant of hydrated electrons, hydrogen atoms and hydroxyl radicals in aqueous solution[END_REF] ns (Figure 2a) showing the very fast formation of an absorbing species. Then, the signal at 305 nm decays slowly and the absorbance at 400 nm remains nearly constant while the signal at 360 nm continues to grow regularly till 300 ns to reach a plateau in our explored time window (Figure 2b). The fast rise in absorbance during the pulse duration is partly due to the production of eaq -but also attributed to reaction R1 and the appearance of BrOH Those results corroborate the kinetics and spectral measurements performed by Zehavi and

eaq -+ N2O N2 + O •- k10 = 9.1  10 9 dm 3 mol -1 s -1 21 (R11) O •-+ H2O • OH + OH - pKa = 11.
Rabani [START_REF] Zehavi | The oxidation of aqueous bromide ions by hydroxyl radicals. A pulse radiolytic investigation[END_REF] and confirm their overall statement that the intermediate BrOH •-absorbs in the same spectral domain as Br2 •-but with a broader spectrum. Indeed, the normalized absorption spectra recorded at 10 ns and 400 ns for the solution containing 0.01 M NaBr and 0.1 M acetone are clearly not identical (Figure 1b). While the spectrum at 400 ns is close to the absorption spectrum reported for Br2 •-, the spectrum at 10 ns seems slightly shifted to the blue and much broader. It is to be noted that a broader spectrum for BrOH •-compared with Br2 •-is not surprising because BrOH •-is a triatomic ion with more degrees of freedom than the diatomic Br2 •-anion and with the ability of H-bond formation with the solvent water molecules, what may induce many solvation micro-environment and energy differences.

Bayesian data analysis. The spectrokinetic data obtained for aqueous solutions containing 0.01 M NaBr and 0.1 M acetone have been analyzed using a Bayesian method for parametric identification. Singular Value Decomposition of the data matrix indicates that its rank is 2.

Considering the strong overlap of the candidate spectra, rotational ambiguity prevents the recovering of unique spectra, even when positivity and/or unimodality constraints are enforced. [START_REF] Ruckebusch | Comprehensive data analysis of femtosecond transient absorption spectra: a review[END_REF] In order to reduce the solution space, we used an explicit model of the kinetic traces taking into account reactions/equilibriums R1 to R6, R8 and R10.

In the present case, the model M of the absorbance data matrix is:

22 BrOH BrOH Br Br M S ( ) C ( ) S ( ) C ( ) n lk l k l k lk t t t t     •- •- •- •- =  + +  + + (4)
where In order to get estimation of the spectra and of their uncertainty, we proceeded in 5 steps:

(1) identification of the Maximum A Posteriori (MAP) parameters with the initial Optimized Parameters set (OPS) and validation of the model (analysis of residuals);

(2) in the presence of improper residuals, addition of new parameters in the OPS on the basis of a sensitivity analysis;

(3) identification of the MAP parameters with the augmented OPS and validation of the model (analysis of residuals);

(4) generation of the possible set of spectra compatible with the full posterior pdf of the OPS;

(5) study of the influence of the external parameters on the recovered spectra called Monte Carlo Uncertainty Propagation (MCUP).

(1) A first attempt was performed with an OPS including four parameters (t, [OH • ]0, [Br -]0 and max(Br2 •-)). The details on the prior pdfs of the parameters and the results, MAP1, are reported in Table 1: a rather good optimal point could be obtained ( 2 R=1.06, P=0.01), with normally distributed residuals. However, the analysis of the residual map revealed a significant structure along the time axis. After considering and rejecting various error sources, we decided to resolve this residual structure by relaxing a minimal set of reaction rate constants.

(2) The minimal set of relevant rate constants was obtained by sensitivity analysis (SA) of the estimated BrOH •-spectrum vs. all uncertain parameters, for which a sample of 500 draws was generated from their prior pdf. The BrOH •-spectrum at 20 wavelengths between 300 and 500 nm was generated for each point of the sample. We used an ANOVA-SA type approach: [START_REF] Saltelli | Sensitivity Analysis[END_REF] the sensitivity coefficients are the fractions of the total output variance apportioned to each input variable. They are obtained analytically from a quadratic leastsquares fit of the response as a function of the inputs. We adapted a procedure proposed by Zhang and Goutsias [START_REF] Zhang | A comparison of approximation techniques for variancebased sensitivity analysis of biochemical reaction systems[END_REF] to the case of inputs with non-Gaussian densities. [START_REF] Martins | Generalized expressions of second and third order for the evaluation of standard measurement uncertainty[END_REF] Among the reaction rates, k1, k-1, k2 and k10 stand out (Supporting Information, Figure S3). Although k-1 has a rather uniform sensitivity index across the wavelength scale, k2 and k10 seem to contribute mostly near the wings of the spectrum. These reaction rate constants have been included in the OPS.

(3) The optimization process was repeated with the augmented OPS (8 parameters) and lead to a new optimal set MAP2 (Table 1). The improvement of the  2 R is significant ( 2 R=1.02, P=0.13), and the structure in the residuals has vanished (Figure 5). The model can be considered as statistically valid, and we can now sample the posterior pdf of the parameters. The spectra and time-dependent concentrations of Br2 •-and BrOH •-obtained at this analytical step are given in Figure S4, Supporting Information.

(4) A posterior sample was generated for the 8 parameters in the OPS (see section 2), and 1000 points were retained to evaluate the mean and standard deviation of the parameters (Table 1). The corresponding set of 1000 numerical spectra for Br2 •-and BrOH •-(Figure 6) has been used to estimate spectral properties by quadratic fit of the log-spectra in the energy scale. The statistics for these results are reported in Table 2. Note that the quadratic model cannot accommodate a hump near the maximum of Br2 •-, which provides an underestimation of max(Br2 •-) by this procedure, when compared with the (preferred) value reported in Table 1.

(5) Finally, the influence of the external parameters (k-2, k3, k-3, k4, k-4, k5, k-5, k6 and k8) was studied by repeating the MAP2 identification, step (3), for a random sample of values of these parameters, drawn from their prior pdf (MCUP sampling). The prior pdfs of the external rate constants are Lognormal distributions using the mean value and uncertainty factor reported in the literature or taken as 20%. As can be seen in Tables 1 and2, the mean values of the MCMC and MCUP procedures are statistically compatible. Moreover, the uncertainty of the inferred parameters due to the external parameters is never larger than the uncertainty obtained by the MCMC procedure, which confirms that the important parameters are effectively in the MAP2-OPS. The uncertainties reported at the MCMC stage can be considered as representative, but in the few cases where both uncertainties are of similar amplitudes, one could use the combination of variances to derive an overall uncertainty. For instance, the global uncertainty on max(BrOH •-) could be estimated as (365 2 + 140 2 ) 1/2 = 390 dm 3 mol -1 cm -1 .

To summarize, the spectrum of BrOH •-could be differentiated from that of Br2 •-(Table 2 and Figure 6). Both spectra peak at similar wavelength (352 vs. 354 nm), but the molar absorption coefficient of BrOH •-at its maximum is 7800 ± 400 dm 3 mol -1 cm -1 , significantly smaller than max(Br2 •-). However, the spectrum of BrOH •-is significantly wider (fwhm = 88 vs. 76 nm) and both species have nearly identical oscillator strengths (ratio OS(BrOH •-)/OS(Br2 •-) = 0.95 ± 0.03). Our results confirm the general trends of the work of Zehavi and Rabani. [START_REF] Zehavi | The oxidation of aqueous bromide ions by hydroxyl radicals. A pulse radiolytic investigation[END_REF] In their attempt to measure the absorption spectrum of BrOH •-, they determined absorbance ratios at a few wavelengths and deduced that the BrOH •-peak seemed broader than the Br2 •-peak; they also estimated the extinction coefficient of BrOH •-to be about 8000 dm 3 mol -1 cm -1 but with an extinction coefficient of 12000 dm 3 mol -1 cm -1 for Br2 •-. However, it is worth noticing that the position of the maximum of Br2 •-absorption spectrum is found slightly blue-shifted compared to the reference value (354 instead of 360 nm) but that this position is in agreement with recent measurements. [START_REF] Lin | Temperature dependence absorption spectra of Br -, Br2°-, and Br3in aqueous solutions[END_REF] Moreover, it is to be noted that the rate constants k1 and k2 have also been slightly adjusted from the literature values and found to be k1 = (8.4 ± 0.5)  10 9 dm 3 mol -1 s -1 and k2 = (8.2 ± 0.6)  10 10 dm 3 mol -1 s -1 .

Quantum calculations. The simulation of the two species Br2

•-and BrOH •-in solution is difficult because of the quantum resonance between two mesomeric forms, BrBr -and Br -Br in the first case, BrOH -and Br -OH in the second case. This makes the elaboration of a classical force field difficult. In a first attempt, we performed CPMD simulations of the solutes with 64 water molecules and found that the interatomic distances of the solutes were unrealistically large and the transition energies much too small. 55 Then, we performed QMMM simulations with a PM3 solute and 250 classical water molecules and found that conversely the interatomic distances of the solutes were unrealistically small. 55 Thus, we used a conventional DFT method with optimization of a set of configurations of the systems Br2 •-(H2O)n and BrOH •-(H2O)n, with n small and the remaining of the solvent modeled with a PCM reaction field in the SMD formalism. 40 As a preliminary step, for Br2 •-, we compared two functionals of the literature: BHHLYP which had already been used on the Br2 •-(H2O)n system in the vacuum 56 and B3LYP. [START_REF] Becke | Density-functional thermochemistry. III. The role of exact exchange[END_REF] We used the pSDD basis set and tested the addition of diffuse Gaussians: s (exponents 0.07, 0.03, 0.01) and p (exponents 0.02, 0.01). Table 3 gives the excitation energy obtained for Br2 •-. It was found that adding diffuse functions had no effect on the calculated excitation energy of Br2 •-and that the B3LYP results were closer to the experimental value (around 360 nm) than the BHHLYP value (Table 3). Consequently, we used B3LYP and the pSDD basis set for all the systems. First, we calculated the transition energies of the solutes with zero explicit water molecules (Tables 4 and5). This means that the solvent is completely modeled by the PCM method. It is found that the two solutes absorb at different wavelengths, with the Br2 •-transition energy (3.33 eV, 372 nm) significantly larger than the BrOH •-one (3.07 eV, 404 nm). These two values differ from the observed value for both solutes (around 3.49 eV, 355 nm). Moreover, the oscillator strength of Br2 •-(0.45) is larger than the oscillator strength of BrOH •-(0.34), but the ratio of these values amounts to 0.75, in qualitative agreement with the measured value (0.9). The present TDDFT calculations yield absorption lines and no band widths.

Nevertheless we note that the Br2 •-solute has six degrees of freedom in the solvent cage while BrOH •-has nine. For this reason we may expect that the absorption band of BrOH •-is larger than that of Br2 •-. This is in agreement with the measurements.

Then, we considered the solutes with a coating of one explicit water molecule. In this case the two solutes display different behaviors: Br2 •-takes up the water molecule in one way only (Figure 7), BrOH •-in three different ways, with the hydrogen bond of the types W → OH, W → Br and W  OH (Figure 8), where W stands for the water molecule. In Table 5 are reported the binding mode of the three BrOH •-(H2O) configurations and the number of equivalent configurations, nconf, as well as the relative energy of the three BrOH •-(H2O) configurations. These energies (Gi = Gi -G1) have been calculated according to: Gi = Gi DFT + Ei CCSD -RTLn nconf (5) Ei CCSD = Ei CCSD -Ei DFT (6) where G DFT is the B3LYP/PCM electronic and nuclear free energy of the solute; RTLn nconf is the conformation entropy of the configuration. E CCSD is a correction using Ei DFT , the B3LYP energy of the solute in the vacuum and Ei CCSD , the CCSD(T) energy in the aug-cc-pvqz basis of the same system. 41 While the three BrOH •-(H2O) configurations lie within 0.08 eV (Table 5), it is striking that these configurations display different absorption wavelengths, between 368 nm (W → OH, ground configuration) and 398 nm (W  OH). This feature is certainly an additional cause of the broader band of BrOH •-compared with Br2 •-.

We also considered coated solutes with 2, 3 and 4 explicit water molecules. In each case we took into account only one configuration, with the lowest energy (Figures 7 and8). The results converge as soon as n = 2 -3 (Tables 4 and5). For n = 2 the absorption wavelengths of Br2 •-(H2O)2 (360 nm) is larger than that of BrOH •-(H2O)2 (354 nm). Note that the corresponding transition energies differ by 0.06 eV only. According to the present measurements the two solutes absorb at similar wavelengths. Nevertheless, these two solutes are different ions and there is no reason for the absorption wavelengths to be equal. Our results suggest that the absorption wavelength of Br2 •-is slightly larger than that of BrOH •-, but it is worth noticing that these results correspond to the lowest energy configuration only.

Figure 9 shows the absorption spectra of the two solutes deduced from the last values (with n = 3) and a convolution using two different Gaussians with full widths at half maximum (fwhm) of 0.75 and 0.9 eV for Br2 •-and BrOH •-, respectively. These fwhm values are empirically taken from the measurements.

CONCLUSION

In the present work, the absorption spectrum of BrOH •-has been investigated both experimentally by pulse radiolysis and theoretically. The measurements and data analysis indicate that BrOH •-absorbs at a similar wavelength as Br2 •-but presents a broader absorption band with a lower molar extinction coefficient (7800  400 dm 3 mol -1 cm -1 compared with 9600 ± 300 dm 3 mol -1 cm -1 ). Quantum chemistry calculations performed on both species corroborate the absorption of BrOH •-in the same spectral region as Br2

ASSOCIATED CONTENT Supporting Information

Data noise analysis; pulse-radiolysis of Ar-purged aqueous solution containing only acetone; sensitivity map; spectra and concentrations versus time of Br2

  9 21 (R12) But, these reactions would have produced • OH for roughly 4.5 ns, what would have complicated the kinetics analysis on the nanosecond time scale.

Figure 1

 1 Figure 1 shows the time evolution of the optical absorption spectrum obtained by pulse radiolysis of N2-purged aqueous solutions containing 0.01 M NaBr and 0.1 M acetone. The optical absorption spectrum registered 0.85 ns after the electron pulse (Figure 1, red) presents two bands: one band located around 360 nm and one band above 450 nm. While the band around 360 nm rises with time, the band in the red decreases rapidly and vanishes. After 10 ns, the spectra present only the absorption band around 360 nm which reaches a maximum at ~300 ns. The band above 450 nm is due to the hydrated electrons (eaq -) which disappears by reaction R8 with acetone. The band around 360 nm is associated with the oxidation of Br -and the formation of BrOH •-and Br2 •-. The time dependence of absorbance at different wavelengths: 305, 360, 400 and 570 nm are shown on Figure 2. The absorption signal at 570 nm (Figure 2a, orange) due to the hydrated electron rises during the electron pulse and then decays exponentially. A pseudo-first

  of k8. Regarding the signals registered at 360, 305 and 400 nm i.e. near the absorption maximum and on the blue and red side of the absorption band, the kinetics profiles are clearly wavelength dependent. Whatever the wavelength, an absorbance has built up during the electron pulse duration and the signals present a fast rise for about 15

  Figures3 and 4depict the spectral changes and kinetics profiles obtained by pulse radiolysis of N2-purged aqueous solutions containing 0.05 M NaBr and 0.1 M acetone. The observed changes are similar to those just described for 0.01 M NaBr solution, but on a shorter time scale. As expected by the increase in Br -concentration, the formation kinetics of BrOH •-and Br2 •-are accelerated. In addition, under these conditions, after 200 ns the absorbance at 360 nm starts to decay slightly due to the slow disappearance of Br2 •-and the formation of Br3 -according to reaction R6.

  -dependent concentration of BrOH •and Br2 •-, respectively; t is an small time-shift compensating for the uncertainty in the exact initial time due to the width of the Cherenkov dip, and nlk is a random variable representing measurement noise. The spectra of both species, to the extinction coefficients, (BrOH •-) and (Br2 •-), multiplied by the optical path length (equal to 1 cm in our case), are obtained wavelength-wise by linear regression.The maximum absorption coefficient of 2 Br S •-, max(Br2 •-), is constrained around 9900 ± 300 dm 3 mol -1 cm -1 , while -BrOH S • is left unconstrained except positivity. The homogeneous chemistry model used to model the kinetic traces is not designed to reproduce the short-time kinetics of the system and the matrix model M (Eq. 4) does not take into account the absorption of the solvated electron. Consequently, the analyzed data matrix is restricted to the time range above 20 ns (the exact value depends on the zero-time shift parameter t) when the solvated electron has vanished. The kinetic traces are calculated by numerical integration of the kinetic model (R1 -R6, R8, R10), with the initial concentrations: [H3O + ]0 = [eaq -]0 = 2 × 10 -5 M, [(CH3)2CO]0 = 0.1 M, [OH • ]0 = 2 × 10 -5 M and [Br -]0 = 0.01 M. The latter two initial concentrations are treated as uncertain with 20% and 5% relative uncertainty, respectively.

Figure 1 .

 1 Figure 1. (a) Optical absorption spectra recorded by pulse radiolysis of N2-purged aqueous solutions containing 0.01 M NaBr and 0.1 M acetone at different time after the electron pulse; (b) Comparison between the normalized absorption spectra recorded at 10 ns and 400 ns.

Figure 2 .

 2 Figure 2. Absorption signals obtained at different wavelengths by pulse radiolysis of N2purged aqueous solutions containing 0.01 M NaBr and 0.1 M acetone on two different time scales: (a) 50 ns, (b) 500 ns.

Figure 3 .

 3 Figure 3. Optical absorption spectra recorded by pulse radiolysis of N2-purged aqueous solutions containing 0.05 M NaBr and 0.1 M acetone at different time after the electron pulse.

Figure 4 .

 4 Figure 4. Absorption signals obtained at different wavelengths recorded by pulse radiolysis of N2-purged aqueous solutions containing 0.05 M NaBr and 0.1 M acetone on two different time scales: (a) 20 ns, (b) 500 ns.

Figure 5 .

 5 Figure 5. Top left: Downsized spectrokinetic data matrix (the absorbance increases from dark blue to dark red); Top right: optimized absorbance matrix giving the best fit (see text for details); Bottom left: Residuals matrix; Bottom right: Q-Q plot comparing the residuals with their theoretical values.

Figure 6 .

 6 Figure 6. Absorption spectra of Br2 •-(black curve) and BrOH •-(red curve) derived from the Bayesian data analysis of the experimental results in Figure 1. The best fit spectra are represented by bold lines.

Figure 7 .

 7 Figure 7. Optimized most stable configurations of Br2 •-(H2O)n with n = 1 to 4.

Figure 8 .

 8 Figure 8. Optimized most stable configurations of BrOH •-(H2O)n with n = 1 (three possibilities) and n = 2 to 4.

Figure 9 .

 9 Figure 9. Calculated absorption spectra of Br2 •-(H2O)3 and BrOH •-(H2O)3 with empirical fwhm values.

Figure 1

 1 Figure 1.

Figure 6 .

 6 Figure 6.

Figure 8 . 32

 832 Figure 8.

Figure 9

 9 Figure 9

  •-. They also reveal the existence of different water-BrOH •-configurations with different transition energies, what may account for the broadening of the spectrum.

Table 1 . Values of the optimized parameters at the various stages of the process.

 1 •-and BrOH •-obtained with the optimal set of parameters MAP2; full references 40 and 41. This information is available free of charge via internet at http://pubs.acs.org.

	Parameter	Prior pdf	MAP(1) MAP(2)	MCMC Mean	MCUP
	t (ns)	Norm(28, 2)	21	27	27.3 (12)	27.17 (70)
	[OH • ]0 (×10 -5 M)	Lnorm(2, 50%)	2.3	2.15	2.21 (4%)	2.221 (4%)
	[Br -]0 (M)	Lnorm(0.010, 5%)	0.098	0.010	0.010 (4%)	0.010 (2%)
	max(Br2 •-) (dm 3 mol -1 cm -1 )	Norm(9900, 300)	9548	9707	9700 (260)	9700 (25)
	k1 (×10 10 M -1 s -1 )	Lnorm(1.1, 10%)	fixed	0.85	0.84 (6%)	0.84 (5%)
	k-1 (×10 7 s -1 )	Lnorm(3.3, 20%)	fixed	2.77	2.77 (10%)	2.77 (6%)
	k2 (×10 6 s -1 )	Lnorm(4.2, 20%)	fixed	8.33	8.17 (8%)	8.01 (7%)
	k10 (×10 8 M -1 s -1 )	Lnorm(1.3, 20%)	fixed	1.64	1.69 (8%)	1.70 (6%)
	 2	R		1.06	1.02	-	1.022 (1)
	P			0.01	0.13	-	-

Norm(x,) corresponds to a normal or Gaussian distribution with x the location of the peak and  the standard deviation; Lnorm(x,y%) stands for Lognormal distributions with x the mean and uncertainty factor taken as a percentage y%;  2 R is the reduced chi-square, i.e. the sum of the weighted residuals divided by the number of degrees of freedom (NDF); P is the probability for a  2 R issued from a chi-square distribution with the same NDF to be larger than the reported value.

Table 2 . Spectral properties of Br2

 2

by Gaussian fit in the energy scale of the numerical spectra generated by the MCMC and MCUP procedures.

  •-and BrOH •-derived

	Derived Spectral Properties	MCMC	MCUP
	max(Br2 •-) (dm 3 mol -1 cm -1 )	9600(260)	9540(30)
	max(Br2 •-) (nm)	354.0	354.0
	(Br2 •-) (nm)	38.122(50)	38.139(40)
	OS(Br2 •-)	7.32(20)	7.278(16)
	max(BrOH •-) (dm 3 mol -1 cm -1 )	7800(365)	7800(140)
	max(BrOH •-) (nm)	352.32(10)	352.363(40)
	( BrOH •-) (nm)	43.71(12)	43.279(80)
	OS(BrOH •-)	6.87(33)	7.02(17)
	OS(BrOH •-) / OS(Br2 •-)	0.938(32)	0.964(25)

max and max correspond to the maximum value of the extinction coefficient and its the position, respectiveley  represents half the full width at half maximum (fwhm/2) of the absorption band ; OS stands for the oscillator strength.

Table 3 . TDDFT results for Br2 •-with two functionals and two basis sets.

 3 E and  represent the transition energy and wavelength, respectively; OS is the associated oscillator strength.

	functional	basis	E (eV)	 (nm)	OS
	BHHLYP	pSDD	3.17	391	0.4976
	BHHLYP	pSDD + diff	3.14	394	0.4868
	B3LYP	pSDD	3.33	372	0.4554
	B3LYP	pSDD + diff	3.31	374	0.4432

Table 4 . TDDFT results for low lying conformations of Br2

 4

Table 5 . TDDFT results for low lying conformations of BrOH •-(H2O)n. The results are obtained with B3LYP and the pSDD basis set.

 5 G is the energy difference between the BrOH •-(H2O) configurations where W stands for the water molecule; E and  represent the transition energy and wavelength, respectively; OS is the associated oscillator strength.

	n	G (eV)	binding mode	E (eV)	 (nm)	OS
			(nconf)
	0	-	-	3.07	404	0.34
	1	0.	W → OH (2)	3.37	368	0.35
	1	+0.025	W → Br (3)	3.19	388	0.34
	1	+0.084	W  OH (1)	3.11	398	0.35
	2	-	-	3.51	354	0.34
	3	-	-	3.50	354	0.33
	4	-	-	3.52	353	0.32
	Exp.	-	-	-	355	-

AUTHOR INFORMATION

Corresponding Author * Tel.: +33 (0)169154511, Fax: +33 (0)169156188, E-mail: isabelle.lampre@u-psud.fr (I.L.)

Notes

The authors declare no competing financial interest.

ACKNOWLEDGMENT

The authors thank Dr B. Levy for fruitful discussions. The fast rise in absorbance during the pulse duration is due to the solvated electron. Then, the disappearance of the solvated electron is observed at 350 nm where its extinction coefficient is greater than that of (CH 3 ) 2 C  OH, but it is not detected at 310 nm where the extinction coefficients are similar.

Supporting Information


domain: info math phys

text:
Samuel Deleplanque

Quantum Computing for solving the 3SAT problem by reduction to the MIS combinatorial optimization problem

Quantum Computing for solving the 3SAT problem by reduction to the MIS combinatorial optimization problem

Introduction

This work tries to anticipate the main issues related to the D-Wave machines topology for solving the 3Sat problem. The polynomial reduction to the Maximum Independent Set Problem (MIS) is employed for solving a 3Sat instance to furnish a less dense graph to the machine. These analog quantum machines, based on the quantum annealing process ( [START_REF] Kadowaki | Quantum annealing in the transverse Ising model[END_REF]), takes a Quadratic Unconstrained Binary Optimization model (QUBO) as input, which is a specific mathematical program easy to build considering the MIS.

Topologies, Embedding and Chains Breaks

Quantum computing will have a significant impact on the Combinatorial Optimization (CO) domain if the universal gate-based quantum machines integrate qubits with a lower error rate than NISQ. Today, to solve CO problems, we obtain more credible results with analog machines such as Pasqal or D-Wave quantum computers which are based on transverse Ising models which are isomorph to the QUBO models. The later type of machines has up to 5k qubits used in an adiabatic process named quantum annealing. The main difficulty is the mapping process (embedding) from the QUBO (or Ising) model to the qubit graph. Indeed the topology is here static (contrary to the Pasqal machines which can dynamically calculate a topology based on a given QUBO) and the mapping process is another optimization problem which can be very complicated to solve even if the instance is small. Figure 1 shows the topologies of the most recent D-Wave machines where the connectivities are 6, 14, 20 from left to right, respectively. EU/MEeting 2023 -Troyes, France, April 17--21, 2023 From a QUBO, the machine will apply a transformation to obtain a larger problem fitting with the qubits graph. Then, this transformation requires more qubits to create logical qubits which correspond, for example, to two physical qubits which must take the same value. However, the measure of these physical qubits can give different values; this is the chain breaks problem.

3Sat polynomial reduction to the MIS and QUBO model

This work considers the 3SAT ≤p MIS reduction with the aim of obtaining a less dense graph than the one we would have by relaxation on all 3Sat constraints xi + xj + xk > 0 into the QUBO. Let's take an easy example to illustrate the transformation from a 3Sat instance to a MIS instance. Considering 3 variables and 3 clauses, we try to solve the following instance:

From the 3 variables we create 9 new variables, one per element of each clause. Taking each variable as a node in a graph, we consider a 3-clique per clause, and we also connect nodes if they correspond to the same initial variables and if one is the complement of the other. Finally, we obtain the graph of the Figure 2. According to this transformation scheme, we generalize the process by noting yij a binary variable such that yij = 1 if yij is in the maximum independent set and 0 otherwise, with i = 1..|C| and j = 1..|X|, and with C the set of clauses, X the set of nodes, E the edges, in a graph G such that G = (X, E). Since we want to maximize the number of nodes (true variables) to be selected in the set while two connected nodes cannot be both selected, the related linear and constrained binary program is:

According to a well-known QUBO transformation rule (see [START_REF] Glover | Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models[END_REF]), the constraints yij + ykl ≤ 1 are equivalent to the quadratic constraints yijykl = 0. Hence, with λ a multiplier, we obtain the following QUBO for the Maximum Independent Set Problem:

The general scheme of resolution is given by the following diagram: Other experiments had been done using different topologies showing the importance of a good topology. For a 3Sat instance with 4 variables and 6 clauses, resulting to a MIS instance with 18 variables, the Chimera topology requires 61 qubits while the Pegasus topology needs 31.

Preliminary Conclusions

Clearly the embedding process is a drag on a good resolution process. In this work, the 3SAT ≤p MIS reduction a been used to obtain a less dense graph in a view of a lighter connectivity (degree) of an instance. However the connectivity of the qubit graph topology is not the only one problem that makes the embedding process time-consuming. Other experiments must be made, especially on a larger set on instances to conclude.

Figure 1 :

 1 Figure 1: 3 D-Wave machines topologies. From left to right: Chimera, Pegasus and Zephir.

Figure 2 :

 2 Figure 2: Graph representation of the MIS obtained from the 3Sat instance.

Figure 3 :

 3 Figure 3: General resolution scheme.

Table 1 :

 1 Results on a 4 variables 11 Clauses instance according to the Annealing Time et the number of Anneals. Machine: Advantage 6.1 (Pegasus topology)

	Annealing	Anneals	Chain Breaks	Opt. Sol.
	Time (µs)	Number	Rate	Number
	0.5	7000	High	92
	1	7000	Average	6
	10	7000	Average	2
	100	2500	Average	3
	1000	500	Average	1
	2000	250	High	0

EU/MEeting 2023 -Troyes, France, April 17--21, 2023

EU/MEeting 2023 -Troyes, France, April 17--21, 2023