Search

We propose and investigate a new method of quantum process tomography (QPT) which we call projected least squares (PLS). In short, PLS consists of first computing the least-squares estimator of the Choi matrix of an unknown channel, and subsequently projecting it onto the convex set of Choi matrices. We consider four experimental setups including direct QPT with Pauli eigenvectors as input and Pauli measurements, and ancilla-assisted QPT with mutually unbiased bases (MUB) measurements. In each case, we provide a closed form solution for the least-squares estimator of the Choi matrix. We propose a novel, two-step method for projecting these estimators onto the set of matrices representing physical quantum channels, and a fast numerical implementation in the form of the hyperplane intersection projection algorithm. We provide rigorous, non-asymptotic concentration bounds, sampling complexities and confidence regions for the Frobenius and trace-norm error of the estimators. For the Frobenius error, the bounds are linear in the rank of the Choi matrix, and for low ranks, they improve the error rates of the least squares estimator by a factor $d^2$, where $d$ is the system dimension. We illustrate the method with numerical experiments involving channels on systems with up to 7 qubits, and find that PLS has highly competitive accuracy and computational tractability., 13+9 pages, 8 figures

In this paper, we consider a parametric density contamination model. We work with a sample of i.i.d. data with a common density, $f^{\star }=(1-\lambda^{\star })\phi +\lambda^{\star }\phi (\cdot-\mu^{\star })$, where the shape $\phi $ is assumed to be known. We establish the optimal rates of convergence for the estimation of the mixture parameters $(\lambda^{\star },\mu^{\star })\in (0,1)\times \mathbb{R}^{d}$. In particular, we prove that the classical parametric rate $1/\sqrt{n}$ cannot be reached when at least one of these parameters is allowed to tend to $0$ with $n$.

Projected least squares (PLS) is an intuitive and numerically cheap technique for quantum state tomography. The method first computes the least-squares estimator (or a linear inversion estimator) and then projects the initial estimate onto the space of states. The main result of this paper equips this point estimator with a rigorous, non-asymptotic confidence region expressed in terms of the trace distance. The analysis holds for a variety of measurements, including 2-designs and Pauli measurements. The sample complexity of the estimator is comparable to the strongest convergence guarantees available in the literature and---in the case of measuring the uniform POVM---saturates fundamental lower bounds.The results are derived by reinterpreting the least-squares estimator as a sum of random matrices and applying a matrix-valued concentration inequality. The theory is supported by numerical simulations for mutually unbiased bases, Pauli observables, and Pauli basis measurements., 5+10 pages, 2+1 figures

International audience; This paper aims at determining under which conditions the semi-discrete optimal transport is twice dierentiable with respect to the parameters of the discrete measure and exhibits numerical applications. The discussion focuses on minimal conditions on the background measure to ensure dierentiability. We provide numerical illustrations in stippling and blue noise problems.

We study the rates of estimation of finite mixing distributions, that is, the parameters of the mixture. We prove that under some regularity and strong identifiability conditions, around a given mixing distribution with $m_{0}$ components, the optimal local minimax rate of estimation of a mixing distribution with $m$ components is $n^{-1/(4(m-m_{0})+2)}$. This corrects a previous paper by Chen [Ann. Statist. 23 (1995) 221–233]. ¶ By contrast, it turns out that there are estimators with a (nonuniform) pointwise rate of estimation of $n^{-1/2}$ for all mixing distributions with a finite number of components.

Magnetic resonance imaging (MRI) is probably one of the most successful application fields of compressed sensing. Despite recent advances, there is still a large discrepancy between theories and most actual implementations. Overall, many important questions related to sampling theory remain open. In this paper, we attack one of them: given a set of sampling constraints (e.g., measuring Fourier coefficients along physically plausible trajectories), how to optimally design a sampling pattern? We first outline three aspects that should be carefully designed by inspecting the literature, namely admissibility, limit of the empirical measure, and coverage speed. To address them jointly, we then propose an original approach which consists of projecting a probability distribution onto a set of admissible measures. The proposed algorithm permits handling arbitrary constraints and automatically generates efficient sampling patterns for MRI as shown on realistic simulations. We achieve a 20-fold undersampling factor...

International audience; This paper deals with the 3 4-discrete 2-Wasserstein optimal transport between two measures, where one is supported by a set of segment and the other one is supported by a set of Dirac masses. We select the most suitable optimization procedure that computes the optimal transport and provide numerical examples of approximation of cloud data by segments.

International audience; Measuring attenuation coefficients is a fundamental problem that can be solved with diverse techniques such as X-ray or optical tomography and lidar. We propose a novel approach based on the observation of a sample from a few different angles. This principle can be used in existing devices such as lidar or various types of fluorescence microscopes. It is based on the resolution of a nonlinear inverse problem. We propose a specific computational approach to solve it and show the well-foundedness of the approach on simulated data. Some of the tools developed are of independent interest. In particular we propose an efficient method to correct attenuation defects, new robust solvers for the lidar equation as well as new efficient algorithms to compute the Lambert W function and the proximal operator of the logsumexp function in dimension 2.

The paper bounds the number of tessellations with T-shaped vertices on a fixed set of $k$ lines: tessellations are efficiently encoded, and algorithms retrieve them, proving injectivity. This yields existence of a completely random T-tessellation, as defined by Ki\^en Ki\^eu et al., and of its Gibbsian modifications. The combinatorial bound is sharp, but likely pessimistic in typical cases., Comment: 34 pages, third revised version. Introduction sections 2 and 3 have been reorganised. No change in results or method of proof

Reducing acquisition time is a crucial challenge for many imaging techniques. Compressed Sensing (CS) theory offers an appealing framework to address this issue since it provides theoretical guarantees on the reconstruction of sparse signals by projection on a low dimensional linear subspace. In this paper, we focus on a setting where the imaging device allows to sense a fixed set of measurements. We first discuss the choice of an optimal sampling subspace (smallest subset) allowing perfect reconstruction of sparse signals. Its standard design relies on the random drawing of independent measurements. We discuss how to select the drawing distribution and show that a mixed strategy involving partial deterministic sampling and independent drawings can help breaking the so-called "coherence barrier". Unfortunately, independent random sampling is irrelevant for many acquisition devices owing to acquisition constraints. To overcome this limitation, the notion of Variable Density Samplers (VDS) is introduced and defined as a stochastic process with a prescribed limit empirical measure. It encompasses samplers based on independent measurements or continuous curves. The latter are crucial to extend CS results to actual applications. Our main contribution lies in two original continuous VDS. The first one relies on random walks over the acquisition space whereas the second one is heuristically driven and rests on the approximate solution of a Traveling Salesman Problem. Theoretical analysis and retrospective CS simulations in magnetic resonance imaging highlight that the TSP-based solution provides improved reconstructed images in terms of signal-to-noise ratio compared to standard sampling schemes (spiral, radial, 3D iid...).

In this work, we revisit fast dimension reduction approaches, as with random projections and random sampling. Our goal is to summarize the data to decrease computational costs and memory footprint of subsequent analysis. Such dimension reduction can be very efficient when the signals of interest have a strong structure, such as with images. We focus on this setting and investigate feature clustering schemes for data reductions that capture this structure. An impediment to fast dimension reduction is that good clustering comes with large algorithmic costs. We address it by contributing a linear-time agglomerative clustering scheme, Recursive Nearest Agglomeration (ReNA). Unlike existing fast agglomerative schemes, it avoids the creation of giant clusters. We empirically validate that it approximates the data as well as traditional variance-minimizing clustering schemes that have a quadratic complexity. In addition, we analyze signal approximation with feature clustering and show that it can remove noise, improving subsequent analysis steps. As a consequence, data reduction by clustering features with ReNA yields very fast and accurate models, enabling to process large datasets on budget. Our theoretical analysis is backed by extensive experiments on publicly-available data that illustrate the computation efficiency and the denoising properties of the resulting dimension reduction scheme., Comment: IEEE Transactions on Pattern Analysis and Machine Intelligence, Institute of Electrical and Electronics Engineers, In press

International audience; Collecting the maximal amount of information in a given scanning time is a major concern in Magnetic Resonance Imaging (MRI) to speed up image acquisition. The hardware constraints (gradient magnitude, slew rate, ...), physical distortions (e.g., off-resonance effects) and sampling theorems (Shannon, compressed sensing) must be taken into account simultaneously, which makes this problem extremely challenging. To date, the main approach to design gradient waveform has consisted of selecting an initial shape (e.g. spiral, radial lines, ...) and then traversing it as fast as possible using optimal control. In this paper, we propose an alternative solution which first consists of defining a desired parameterization of the trajectory and then of optimizing for minimal deviation of the sampling points within gradient constraints. This method has various advantages. First, it better preserves the density of the input curve which is critical in sampling theory. Second, it allows to smooth high curvature areas making the acquisition time shorter in some cases. Third, it can be used both in the Shannon and CS sampling theories. Last, the optimized trajectory is computed as the solution of an efficient iterative algorithm based on convex programming. For piecewise linear trajectories, as compared to optimal control reparameterization, our approach generates a gain in scanning time of 10% in echo planar imaging while improving image quality in terms of signal-to-noise ratio (SNR) by more than 6 dB. We also investigate original trajectories relying on traveling salesman problem solutions. In this context, the sampling patterns obtained using the proposed projection algorithm are shown to provide significantly better reconstructions (more than 6 dB) while lasting the same scanning time.

International audience; We consider the problem of projecting a probability measure π on a set MN of Radon measures. The projection is defined as a solution of the following variational problem: inf µ∈M N h (µ − π) 2 2 , where h ∈ L 2 (Ω) is a kernel, Ω ⊂ R d and denotes the convolution operator. To motivate and illustrate our study, we show that this problem arises naturally in various practical image rendering problems such as stippling (representing an image with N dots) or continuous line drawing (representing an image with a continuous line). We provide a necessary and sufficient condition on the sequence (MN) N ∈N that ensures weak convergence of the projections (µ * N) N ∈N to π. We then provide a numerical algorithm to solve a discretized version of the problem and show several illustrations related to computer-assisted synthesis of artistic paintings/drawings.

Analysis of fluorescence lifetime imaging microscopy (FLIM) and Forster resonance energy transfer (FRET) experiments in living cells is usually based on mean lifetimes computations. However, these mean lifetimes can induce misinterpretations. We propose in this work the implementation of the transportation distance for FLIM and FRET experiments in vivo. This non-fitting indicator, which is easy to compute, reflects the similarity between two distributions and can be used for pixels clustering to improve the estimation of the FRET parameters. We study the robustness and the discriminating power of this transportation distance, both theoretically and numerically. In addition, a comparison study with the largely used mean lifetime differences is performed. We finally demonstrate practically the benefits of the transportation distance over the usual mean lifetime differences for both FLIM and FRET experiments in living cells.

We introduce a new partial order on the class of stochastically monotone Markov kernels having a given stationary distribution $\pi$ on a given finite partially ordered state space $\mathcal{X}$. When $K\preceq L$ in this partial order we say that $K$ and $L$ satisfy a comparison inequality. We establish that if $K_1,\ldots,K_t$ and $L_1,\ldots,L_t$ are reversible and $K_s\preceq L_s$ for $s=1,\ldots,t$, then $K_1\cdots K_t\preceq L_1\cdots L_t$. In particular, in the time-homogeneous case we have $K^t\preceq L^t$ for every $t$ if $K$ and $L$ are reversible and $K\preceq L$, and using this we show that (for suitable common initial distributions) the Markov chain $Y$ with kernel $K$ mixes faster than the chain $Z$ with kernel $L$, in the strong sense that at every time $t$ the discrepancy - measured by total variation distance or separation or $L^2$-distance - between the law of $Y_t$ and $\pi$ is smaller than that between the law of $Z_t$ and $\pi$. Using comparison inequalities together with specialized arguments to remove the stochastic monotonicity restriction, we answer a question of Persi Diaconis by showing that, among all symmetric birth-and-death kernels on the path $\mathcal{X}=\{0,\ldots,n\}$, the one (we call it the uniform chain) that produces fastest convergence from initial state 0 to the uniform distribution has transition probability 1/2 in each direction along each edge of the path, with holding probability 1/2 at each endpoint., Comment: Published in at http://dx.doi.org/10.1214/12-AAP886 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

It was shown in [T. Morimae, Phys. Rev. A {\bf81}, 060307(R) (2010)] that the gate fidelity of an inaccurate one-way quantum computation is upper bounded by a decreasing function of the amount of entanglement in the register. This means that a strong entanglement causes the low gate fidelity in the one-way quantum computation with inaccurate measurements. In this paper, we derive similar entanglement-fidelity relations for the inaccurate ancilla-driven quantum computation. These relations again imply that a strong entanglement in the register causes the low gate fidelity in the ancilla-driven quantum computation if the measurements on the ancilla are inaccurate., 8 pages, 7 figures

We extend our previous results on local asymptotic normality (LAN) for qubits, to quantum systems of arbitrary finite dimension $d$. LAN means that the quantum statistical model consisting of $n$ identically prepared $d$-dimensional systems with joint state $\rho^{\otimes n}$ converges as $n\to\infty$ to a statistical model consisting of classical and quantum Gaussian variables with fixed and known covariance matrix, and unknown means related to the parameters of the density matrix $\rho$. Remarkably, the limit model splits into a product of a classical Gaussian with mean equal to the diagonal parameters, and independent harmonic oscillators prepared in thermal equilibrium states displaced by an amount proportional to the off-diagonal elements. As in the qubits case, LAN is the main ingredient in devising a general two step adaptive procedure for the optimal estimation of completely unknown $d$-dimensional quantum states. This measurement strategy shall be described in a forthcoming paper., Comment: 64 pages

We propose an adaptive, two steps strategy, for the estimation of mixed qubit states. We show that the strategy is optimal in a local minimax sense for the trace norm distance as well as other locally quadratic figures of merit. Local minimax optimality means that given $n$ identical qubits, there exists no estimator which can perform better than the proposed estimator on a neighborhood of size $n^{-1/2}$ of an arbitrary state. In particular, it is asymptotically Bayesian optimal for a large class of prior distributions. We present a physical implementation of the optimal estimation strategy based on continuous time measurements in a field that couples with the qubits. The crucial ingredient of the result is the concept of local asymptotic normality (or LAN) for qubits. This means that, for large $n$, the statistical model described by $n$ identically prepared qubits is locally equivalent to a model with only a classical Gaussian distribution and a Gaussian state of a quantum harmonic oscillator. The term `local' refers to a shrinking neighborhood around a fixed state $\rho_{0}$. An essential result is that the neighborhood radius can be chosen arbitrarily close to $n^{-1/4}$. This allows us to use a two steps procedure by which we first localize the state within a smaller neighborhood of radius $n^{-1/2+\epsilon}$, and then use LAN to perform optimal estimation., Comment: 32 pages, 3 figures, to appear in Commun. Math. Phys

In a recent paper, Buscemi and al. defined a notion of clean positive operator valued measures (POVMs). We here characterize which POVMs are clean in some class that we call quasi-qubit POVMs, namely POVMs whose elements are all rank-one or full-rank. We give an algorithm to check whether a given quasi-qubit POVM satisfies to this condition. We describe explicitely all the POVMs that are clean for the qubit. On the way we give a sufficient condition for a general POVM to be clean., 15 pages, Much of a sequel to quant-ph/0505095 Rewriting of the article deeply improving (I hope) the presentation. Accepted for publication in Journal of Physics A

In connection with optimal state determination for two qubits, the question was raised about the maximum number of pairwise complementary reductions. The main result of the paper tells that the maximum number is 4, that is, if A1, A2,... Ak are pairwise complementary (or quasi-orthogonal) subalgebras of the algebra of all 4x4$ matrices and they are isomorphic to the algebra of all 2x2 matrices, then k is at most 4. In the way to this result, contributions are made to the understanding of the structure of complementary reductions., Comment: 7 pages, key words: mutually unbiased bases, unbiased measurements, complementary subalgebras, Cartan decomposition, Pauli matrices

We consider n identically prepared qubits and study the asymptotic properties of the joint state \rho^{\otimes n}. We show that for all individual states \rho situated in a local neighborhood of size 1/\sqrt{n} of a fixed state \rho^0, the joint state converges to a displaced thermal equilibrium state of a quantum harmonic oscillator. The precise meaning of the convergence is that there exist physical transformations T_{n} (trace preserving quantum channels) which map the qubits states asymptotically close to their corresponding oscillator state, uniformly over all states in the local neighborhood. A few consequences of the main result are derived. We show that the optimal joint measurement in the Bayesian set-up is also optimal within the pointwise approach. Moreover, this measurement converges to the heterodyne measurement which is the optimal joint measurement of position and momentum for the quantum oscillator. A problem of local state discrimination is solved using local asymptotic normality., Comment: 16 pages, 3 figures, published version

We give an explicit procedure based on entangled input states for estimating a $SU(d)$ operation $U$ with rate of convergence $1/N^2$ when sending $N$ particles through the device. We prove that this rate is optimal. We also evaluate the constant $C$ such that the asymptotic risk is $C/N^2$. However other strategies might yield a better const ant $C$., Comment: 8 pages, 1 figure Rewritten version, accepted for publication in Phys. Rev. A. The introduction is richer, the "tool section" on group representations has been suppressed, and a section proving that the 1/N^2 rate is optimum has been added

We derive the optimal measurement for quantum-state discrimination without a priori probabilities, i.e., in a minimax strategy instead of the usually considered Bayesian one. We consider both minimal-error and unambiguous discrimination problems, and provide the relation between the optimal measurements according to the two schemes. We show that there are instances in which the minimum risk cannot be achieved by an orthogonal measurement, and this is a common feature of the minimax estimation strategy.

We consider the problem of optimally discriminating two Pauli channels in the minimax strategy, maximizing the smallest of the probabilities of correct identification of the channel. We find the optimal input state at the channel and show the conditions under which using entanglement strictly enhances distinguishability. We finally compare the minimax strategy with the Bayesian one., Comment: 9 pages, 3 figures

International audience; Le stippling est un problème qui a beaucoup progressé dernièrement grâce à l'introduction de méthodes variationnelles. On s'intéresse ici à deux types de formulations. L'une repose sur une distance L 2 entre mesures et fait appel à des outils d'analyse harmonique appliquée. L'autre repose sur la distance de Wasserstein et fait appel à des outils de géométrie algorithmique. Différentes méthodes de résolution et de discrétisation sont comparées et nous présentons leurs atouts et leurs limitations. Abstract-Stippling is a problem that recently found elegant and efficient solutions thanks to the introduction of variational methods. The aim of this paper is to compare two state-of-the-art approaches: one is based on the minimization of an L 2 norm (which links to applied harmonic analysis), while the other is based on the Wasserstein distance (which links to computational geometry).

International audience; We propose a fast and scalable algorithm to project a given density on a set of structured measures defined over a compact 2D domain. The measures can be discrete or supported on curves for instance. The proposed principle and algorithm are a natural generalization of previous results revolving around the generation of blue-noise point distributions, such as Lloyd's algorithm or more advanced techniques based on power diagrams. We analyze the convergence properties and propose new approaches to accelerate the generation of point distributions. We also design new algorithms to project curves onto spaces of curves with bounded length and curvature or speed and acceleration. We illustrate the algorithm's interest through applications in advanced sampling theory, non-photorealistic rendering and path planning.

This thesis focuses on the approximation for the 2-Wasserstein metric of probability measures by structured measures. The set of structured measures under consideration is made of consistent discretizations of measures carried by a smooth curve with a bounded speed and acceleration. We compare two different types of approximations of the curve: piecewise constant and piecewise linear. For each of these methods, we develop fast and scalable algorithms to compute the 2-Wasserstein distance between a given measure and the structured measure. The optimization procedure reveals new theoretical and numerical challenges, it consists of two steps: first the computation of the 2-Wasserstein distance, second the optimization of the parameters of structure. This work is initially motivated by the design of trajectories in MRI acquisition, however we provide new applications of these methods., Cette thèse s’intéresse à l’approximation pour la métrique de 2-Wasserstein de mesures de probabilité par une mesure structurée. Les mesures structurées étudiées sont des discrétisations consistantes de mesures portées par des courbes continues à vitesse et à accélération bornées. Nous comparons deux types d’approximations pour ces courbes continues : l’approximation constante par morceaux et linéaire par morceaux. Pour chaque méthode, des algorithmes rapides et fonctionnant pour une discrétisation fine ont été développés. Le problème d’approximation se divise en deux étapes avec leurs propres défis théoriques et algorithmiques : le calcul de la distance de Wasserstein 2 et son optimisation par rapport aux paramètres de structure. Ce travail est initialement motivé par la génération de trajectoires d’IRM en acquisition compressée, toutefois nous donnons de nouvelles applications potentielles pour ces méthodes.