The original motivation to build a quantum computer came from Feynman, who imagined a machine capable of simulating generic quantum mechanical systems–-a task that is believed to be intractable for classical computers. Such a machine could have farreaching applications in the simulation of many-body quantum physics in condensed-matter, chemical and high-energy systems. Part of Feynman's challenge was met by Lloyd, who showed how to approximately decompose the time evolution operator of interacting quantum particles into a short sequence of elementary gates, suitable for operation on a quantum computer. However, this left open the problem of how to simulate the equilibrium and static properties of quantum systems. This requires the preparation of ground and Gibbs states on a quantum computer. For classical systems, this problem is solved by the ubiquitous Metropolis algorithm, a method that has basically acquired a monopoly on the simulation of interacting particles. Here we demonstrate how to implement a quantum version of the Metropolis algorithm. This algorithm permits sampling directly from the eigenstates of the Hamiltonian, and thus evades the sign problem present in classical simulations. A small-scale implementation of this algorithm should be achievable with today's technology.

1 aTemme, K1 aOsborne, T J1 aVollbrecht, K1 aPoulin, D1 aVerstraete, F uhttp://www.physique.usherbrooke.ca/pages/sites/default/files/poulin/TOVP11a.pdf00466nas a2200121 4500008004100000245009900041210006900140100001400209700001800223700002200241700002200263856005900285 2011 eng d00aQuantum simulation of time-dependent Hamiltonians and the convenient illusion of Hilbert space0 aQuantum simulation of timedependent Hamiltonians and the conveni1 aPoulin, D1 aQuarry, Angie1 aSomma, Rolando, D1 aVerstraete, Frank uhttps://www.physique.usherbrooke.ca/pages/en/node/620800825nas a2200133 4500008004100000245005500041210005500096520040000151653001900551100001900570700002900589700001400618856005900632 2011 eng d00aUniversal topological phase of 2D stabilizer codes0 aUniversal topological phase of 2D stabilizer codes3 aTwo topological phases are equivalent if they are connected by a local unitary transformation. In this sense, classifying topological phases amounts to classifying long-range entanglement patterns. We show that all 2D topological stabilizer codes are equivalent to several copies of one universal phase: Kitaev's topological code. Error correction benefits from the corresponding local mappings.10aTopological QC1 aBombin, Hector1 aDuclos-Cianci, Guillaume1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/798801732nas a2200157 4500008004100000245010400041210006900145300001100214490000700225520121700232653002301449653001501472100001401487700001401501856005901515 2010 eng d00aCoarse grained belief propagation for simulation of interacting quantum systems at all temperatures0 aCoarse grained belief propagation for simulation of interacting a0541060 v813 aWe continue our numerical study of quantum belief propagation initiated in \cite{PB08a}. We demonstrate how the method can be expressed in terms of an effective thermal potential that materializes when the system presents quantum correlations, but is insensitive to classical correlations. The thermal potential provides an efficient means to assess the precision of belief propagation on graphs with no loops. We illustrate these concepts using the one-dimensional quantum Ising model and compare our results with exact solutions. We also use the method to study the transverse field quantum Ising spin glass for which we obtain a phase diagram that is largely in agreement with the one obtained in \cite{LSS07a} using a different approach. Finally, we introduce the coarse grained belief propagation (CGBP) algorithm to improve belief propagation at low temperatures. This method combines the reliability of belief propagation at high temperatures with the ability of entanglement renormalization to efficiently describe low energy subspaces of quantum systems with local interactions. With CGBP, thermodynamic properties of quantum systems can be calculated with a high degree of accuracy at all temperatures.10aBelief propagation10aSimulation1 aBilgin, E1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/624101579nas a2200217 4500008004100000245003900041210003900080300000800119490000600127520102700133100001401160700001601174700001701190700001301207700001301220700001801233700002301251700001401274700001401288856005901302 2010 eng d00aEfficient quantum state tomography0 aEfficient quantum state tomography a1490 v13 aQuantum state tomography–-deducing quantum states from measured data–-is the gold standard for verification and benchmarking of quantum devices. It has been realized in systems with few components, but for larger systems it becomes unfeasible because the number of measurements and the amount of computation required to process them grows exponentially in the system size. Here, we present two tomography schemes that scale much more favourably than direct tomography with system size. One of them requires unitary operations on a constant number of subsystems, whereas the other requires only local measurements together with more elaborate post-processing. Both rely only on a linear number of experimental operations and post-processing that is polynomial in the system size. These schemes can be applied to a wide range of quantum states, in particular those that are well approximated by matrix product states. The accuracy of the reconstructed states can be rigorously certified without any a priori assumptions.1 aCramer, M1 aPlenio, M B1 aFlammia, S T1 aSomma, R1 aGross, D1 aBartlett, S D1 aLandon-Cardinal, O1 aPoulin, D1 aLiu, Y -K uhttps://www.physique.usherbrooke.ca/pages/en/node/623501065nas a2200157 4500008004100000245004800041210004800089300001100137490000800148520060900156653002100765653001900786100002900805700001400834856005900848 2010 eng d00aFast decoders for topological quantum codes0 aFast decoders for topological quantum codes a0505040 v1043 aWe present a family of algorithms, combining real-space renormalization methods and belief propagation, to estimate the free energy of a topologically ordered system in the presence of defects. Such an algorithm is needed to preserve the quantum information stored in the ground space of a topologically ordered system and to decode topological error-correcting codes. For a system of linear size $\ell$, our algorithm runs in time $łog\ell$ compared to $\ell^6$ needed for the minimum-weight perfect matching algorithm previously used in this context and achieves a higher depolarizing error threshold.10aError correction10aTopological QC1 aDuclos-Cianci, Guillaume1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/623401577nas a2200157 4500008004100000245009400041210006900135300001100204490000700215520107900222100002001301700001201321700001401333700001301347856005901360 2010 eng d00aInformation preserving structures: a general framework for quantum zero-error information0 aInformation preserving structures a general framework for quantu a0623060 v823 aQuantum systems carry information. Quantum theory supports at least two distinct kinds of information (classical and quantum), and a variety of different ways to encode and preserve information in physical systems. A system's ability to carry information is constrained and defined by the noise in its dynamics. This paper introduces an operational framework, using informationpreserving structures to classify all the kinds of information that can be perfectly (i.e., with zero error) preserved by quantum dynamics. We prove that every perfectly preserved code has the same structure as a matrix algebra, and that preserved information can always be corrected. We also classify distinct operational criteria for preservation (e.g., ``noiseless'', ``unitarily correctible'', etc.) and introduce two new and natural criteria for measurement-stabilized and unconditionally preserved codes. Finally, for several of these operational critera, we present efficient [polynomial in the state-space dimension] algorithms to find all of a channel's information-preserving structures.1 aBlume-Kohout, R1 aNg, H K1 aPoulin, D1 aViola, L uhttps://www.physique.usherbrooke.ca/pages/en/node/624001090nas a2200121 4500008004100000245007600041210006900117300001100186490000800197520069000205100001400895856005900909 2010 eng d00aLieb-Robinson bound and locality for general Markovian quantum dynamics0 aLiebRobinson bound and locality for general Markovian quantum dy a1904010 v1043 aThe Lieb-Robinson bound shows the existence of a maximum speed of signal propagation in discrete quantum mechanical systems with local interactions. This generalizes the concept of relativistic causality beyond field theory, and provides a powerful tool in theoretical condensed matter physics and quantum information science. Here, we extend the scope of this seminal result by considering general Markovian quantum evolution, where we prove that an equivalent bound holds. In addition, we use the generalized bound to demonstrate that correlations in the stationary state of a Markov process decay on a length-scale set by the Lieb-Robinson velocity and the system's relaxation time.1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/620701223nas a2200169 4500008004100000245007100041210006900112300001100181490000800192520070900200653002100909653002000930100001400950700001400964700001600978856005900994 2010 eng d00aTradeoffs for reliable quantum information storage in {2D} systems0 aTradeoffs for reliable quantum information storage in 2D systems a0505030 v1043 aWe ask whether there are fundamental limits on storing quantum information reliably in a bounded volume of space. To investigate this question, we study quantum error correcting codes specified by geometrically local commuting constraints on a 2D lattice of finite-dimensional quantum particles. For these 2D systems, we derive a tradeoff between the number of encoded qubits $k$, the distance of the code $d$, and the number of particles $n$. It is shown that $kd^2=O(n)$ where the coefficient in $O(n)$ depends only on the locality of the constraints and dimension of the Hilbert spaces describing individual particles. The analogous tradeoff for the classical information storage is $k\sqrt{d} =O(n)$.10aError correction10aSelf correcting1 aBravyi, S1 aPoulin, D1 aTerhal, B M uhttps://www.physique.usherbrooke.ca/pages/en/node/623700498nas a2200157 4500008004100000245006900041210006900110300000800179100001400187700001400201700001600215700001700231700001800248700001500266856005900281 2010 eng d00aTradeoffs for reliable quantum information storage in 2D systems0 aTradeoffs for reliable quantum information storage in 2D systems a1251 aBravyi, S1 aPoulin, D1 aTerhal, B M1 aHorodecki, R1 aKilin, Ya., S1 aKowalik, J uhttps://www.physique.usherbrooke.ca/pages/en/node/623601147nas a2200157 4500008004100000245007900041210006900120300001100189490000800200520065200208653001500860653002300875100001400898700001800912856005900930 2009 eng d00aPreparing ground states of quantum many-body systems on a quantum computer0 aPreparing ground states of quantum manybody systems on a quantum a1305030 v1023 aPreparing the ground state of a system of interacting classical particles is an NP-hard problem. Thus, there is in general no better algorithm to solve this problem than exhaustively going through all $N$ configurations of the system to determine the one with lowest energy, requiring a running time proportional to $N$. A quantum computer, if it could be built, could solve this problem in time $\sqrt N$. Here, we present a powerful extension of this result to the case of interacting {\em quantum} particles, demonstrating that a quantum computer can prepare the ground state of a quantum system as efficiently as it does for classical systems.10aComplexity10aQuantum simulation1 aPoulin, D1 aWocjan, Pawel uhttps://www.physique.usherbrooke.ca/pages/en/node/620601842nas a2200169 4500008004100000245003100041210003000072300000900102490000700111520141000118653002101528653001601549100001401565700001801579700001601597856005901613 2009 eng d00aQuantum serial turbo-codes0 aQuantum serial turbocodes a27760 v553 aWe present a theory of quantum serial turbo-codes, describe their iterative decoding algorithm, and study their performances numerically on a depolarization channel. Our construction offers several advantages over quantum LDPC codes. First, the Tanner graph used for decoding is free of 4-cycles that deteriorate the performances of iterative decoding. Secondly, the iterative decoder makes explicit use of the code's degeneracy. Finally, there is complete freedom in the code design in terms of length, rate, memory size, and interleaver choice. We define a quantum analogue of a state diagram that provides an efficient way to verify the properties of a quantum convolutional code, and in particular its recursiveness and the presence of catastrophic error propagation. We prove that all recursive quantum convolutional encoder have catastrophic error propagation. In our constructions, the convolutional codes have thus been chosen to be non-catastrophic and non-recursive. While the resulting families of turbo-codes have bounded minimum distance, from a pragmatic point of view the effective minimum distances of the codes that we have simulated are large enough not to degrade the iterative decoding performance up to reasonable word error rates and block sizes. With well chosen constituent convolutional codes, we observe an important reduction of the word error rate as the code length increases.10aError correction10aTurbo Codes1 aPoulin, D1 aTillich, J -P1 aOllivier, H uhttps://www.physique.usherbrooke.ca/pages/en/node/622001008nas a2200133 4500008004100000245010100041210006900142300001100211490000800222520055300230100001400783700001800797856005900815 2009 eng d00aSampling from the quantum Gibbs state and evaluating partition functions with a quantum computer0 aSampling from the quantum Gibbs state and evaluating partition f a2205020 v1033 aWe present a quantum algorithm to prepare the thermal Gibbs state of interacting quantum systems. This algorithm sets a universal upper bound $D^\alpha$ on the thermalization time of a quantum system, where $D$ is the system's Hilbert space dimension and $\alpha łeq \frac 12$ is proportional to the Helmholtz free energy density of the system. We also derive an algorithm to evaluate the partition function of a quantum system in a time proportional to the system's thermalization time and inversely proportional to the targeted accuracy squared.1 aPoulin, D1 aWocjan, Pawel uhttps://www.physique.usherbrooke.ca/pages/en/node/620501370nas a2200157 4500008004100000245013300041210006900174300001100243490000700254520082600261653002301087653001501110100001401125700001401139856005901153 2008 eng d00aBelief propagation algorithm for computing correlation functions in finite-temperature quantum many-body systems on loopy graphs0 aBelief propagation algorithm for computing correlation functions a0523180 v773 aBelief propagation –- a powerful heuristic method to solve inference problems involving a large number of random variables –- was recently generalized to quantum theory. Like its classical counterpart, this algorithm is exact on trees when the appropriate independence conditions are met and is expected to provide reliable approximations when operated on loopy graphs. In this paper, we benchmark the performances of loopy quantum belief propagation (QBP) in the context of finite-temperature quantum many-body physics. Our results indicate that QBP provides reliable estimates of the high-temperature correlation function when the typical loop size in the graph is large. As such, it is suitable e.g. for the study of quantum spin glasses on Bethe lattices and the decoding of sparse quantum error correction codes.10aBelief propagation10aSimulation1 aPoulin, D1 aBilgin, E uhttps://www.physique.usherbrooke.ca/pages/en/node/621801301nas a2200157 4500008004100000245005400041210004700095300000800142490000600150520086900156653002301025653000901048100001401057700001301071856005901084 2008 eng d00aOn the iterative decoding of sparse quantum codes0 aiterative decoding of sparse quantum codes a9860 v83 aWe address the problem of decoding sparse quantum error correction codes. For Pauli channels, this task can be accomplished by a version of the belief propagation algorithm used for decoding sparse classical codes. Quantum codes pose two new challenges however. Firstly, their Tanner graph unavoidably contain small loops which typically undermines the performance of belief propagation. Secondly, sparse quantum codes are by definition highly degenerate. The standard belief propagation algorithm does not exploit this feature, but rather it is impaired by it. We propose heuristic methods to improve belief propagation decoding, specifically targeted at these two problems. While our results exhibit a clear improvement due to the proposed heuristic methods, they also indicate that the main source of errors in the quantum coding scheme remains in the decoding.10aBelief propagation10aLDPC1 aPoulin, D1 aChung, Y uhttps://www.physique.usherbrooke.ca/pages/en/node/621901771nas a2200181 4500008004100000245005200041210005200093300000900145490000800154520127500162653002301437653000901460653001501469653001601484100001601500700001401516856005901530 2008 eng d00aQuantum graphical models and belief propagation0 aQuantum graphical models and belief propagation a18990 v3233 aBelief Propagation algorithms acting on Graphical Models of classical probability distributions, such as Markov Networks, Factor Graphs and Bayesian Networks, are amongst the most powerful known methods for deriving probabilistic inferences amongst large numbers of random variables. This paper presents a generalization of these concepts and methods to the quantum case, based on the idea that quantum theory can be thought of as a noncommutative, operator-valued, generalization of classical probability theory. Some novel characterizations of quantum conditional independence are derived, and definitions of Quantum n-Bifactor Networks, Markov Networks, Factor Graphs and Bayesian Networks are proposed. The structure of Quantum Markov Networks is investigated and some partial characterization results are obtained, along the lines of the Hammersely-Clifford theorem. A Quantum Belief Propagation algorithm is presented and is shown to converge on 1-Bifactor Networks and Markov Networks when the underlying graph is a tree. The use of Quantum Belief Propagation as a heuristic algorithm in cases where it is not known to converge is discussed. Applications to decoding quantum error correcting codes and to the simulation of many-body quantum systems are described.10aBelief propagation10aLDPC10aSimulation10aTurbo Codes1 aLeifer, M S1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/622601342nas a2200169 4500008004100000245005300041210005300094300001100147490000700158520087100165653001601036653001201052653002001064100001501084700001401099856005901113 2008 eng d00aQuantum reference frames and deformed symmetries0 aQuantum reference frames and deformed symmetries a1040120 v773 aIn the context of constrained quantum mechanics, reference systems are used to construct relational observables that are invariant under the action of the symmetry group. Upon measurement of a relational observable, the reference system undergoes an unavoidable measurement ``back-action" that modifies its properties. In a quantum-gravitational setting, it has been argued that such a back-action may produce effects that are described at an effective level as a form of deformed (or doubly) special relativity. We examine this possibility using a simple constrained system that has been extensively studied in the context of quantum information. While our conclusions support the idea of a symmetry deformation, they also reveal a host of other effects that may be relevant to the context of quantum gravity, and could potentially conceal the symmetry deformation.10aFoundations10aGravity10aReference frame1 aGirelli, F1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/623202082nas a2200157 4500008004100000245003100041210003000072260000900102520165700111653002101768653001601789100001401805700002501819700002101844856005901865 2008 eng d00aQuantum serial turbo-codes0 aQuantum serial turbocodes bIEEE3 aWe present a theory of quantum serial turbo-codes and study their performance numerically on a depolarization channel. These codes can be considered as a generalization of classical serial turbo-codes. As their classical cousins, they can be iteratively decoded and with well chosen constituent convolutional codes, we observe an important reduction of the word error rate as the number of encoded qubits increases. Our construction offers several advantages over quantum LDPC codes. First, the Tanner graph used for decoding can be chosen to be free of 4-cycles that deteriorate the performances of iterative decoding. Secondly, the iterative decoder makes explicit use of the code's degeneracy. Finally, there is complete freedom in the code design in terms of length, rate, memory size, and interleaver choice. We address two issues related to the encoding of convolutional codes that are directly relevant for turbo-codes, namely the character of being recursive and non-catastrophic. We define a quantum analogue of a state diagram that provides an efficient way to verify these properties on a given quantum convolutional encoder. Unfortunately, we also prove that all recursive quantum convolutional encoder have catastrophic error propagation. In our constructions, the convolutional codes have thus been chosen to be non-catastrophic and non-recursive. While the resulting families of turbo-codes have bounded minimum distance, from a pragmatic point of view the effective minimum distances of the codes that we have simulated are large enough for not degrading iterative decoding performance up to reasonable word error rates and block sizes.10aError correction10aTurbo Codes1 aPoulin, D1 aTillich, Jean-Pierre1 aOllivier, Harold uhttps://www.physique.usherbrooke.ca/pages/en/node/620401183nas a2200169 4500008004100000245006400041210006000105300001100165490000800176520069000184653002100874100002000895700001200915700001400927700001300941856005900954 2008 eng d00aThe structure of preserved information in quantum processes0 astructure of preserved information in quantum processes a0305010 v1003 aWe introduce a general operational characterization of information-preserving structures (IPS) – encompassing noiseless subsystems, decoherence-free subspaces, pointer bases, and error-correcting codes – by demonstrating that they are isometric to fixed points of unital quantum processes. Using this, we show that every IPS is a matrix algebra. We further establish a structure theorem for the fixed states and observables of an arbitrary process, which unifies the Schrödinger and Heisenberg pictures, places restrictions on physically allowed kinds of information, and provides an efficient algorithm for finding all noiseless and unitarily noiseless subsystems of the process.10aError correction1 aBlume-Kohout, R1 aNg, H K1 aPoulin, D1 aViola, L uhttps://www.physique.usherbrooke.ca/pages/en/node/623901236nas a2200157 4500008004100000245008900041210006900130300001100199490000700210520074100217653002100958653000900979100001700988700001401005856005901019 2007 eng d00aAlgebraic and information-theoretic conditions for operator quantum error-correction0 aAlgebraic and informationtheoretic conditions for operator quant a0643040 v753 aOperator quantum error-correction is a technique for robustly storing quantum information in the presence of noise. It generalizes the standard theory of quantum error-correction, and provides a unified framework for topics such as quantum error-correction, decoherence-free subspaces, and noiseless subsystems. This paper develops (a) easily applied algebraic and information-theoretic conditions which characterize when operator quantum error-correction is feasible; (b) a representation theorem for a class of noise processes which can be corrected using operator quantum error-correction; and (c) generalizations of the coherent information and quantum data processing inequality to the setting of operator quantum error-correction.10aError correction10aOQEC1 aNielsen, M A1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/622301143nas a2200145 4500008004100000245006000041210006000101490000700161520070900168653001200877653002000889100001500909700001400924856005900938 2007 eng d00aDeformed symmetries from quantum relational observables0 aDeformed symmetries from quantum relational observables0 v683 aDeformed Special Relativity (DSR) is a candidate phenomenological theory to describe the Quantum Gravitational (QG) semi-classical regime. A possible interpretation of DSR can be derived from the notion of deformed reference frame. Observables in (quantum) General Relativity can be constructed from (quantum) reference frame – a physical observable is then a relation between a system of interest and the reference frame. We present a toy model and study an example of such quantum relational observables. We show how the intrinsic quantum nature of the reference frame naturally leads to a deformation of the symmetries, comforting DSR to be a good candidate to describe the QG semi-classical regime.10aGravity10aReference frame1 aGirelli, F1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/623101615nas a2200145 4500008004100000245004200041210004200083300000800125490000600133520122500139653002001364100001401384700001201398856005901410 2007 eng d00aDynamics of a Quantum Reference Frame0 aDynamics of a Quantum Reference Frame a1560 v93 aWe analyze a quantum mechanical gyroscope which is modeled as a large spin and used as a reference against which to measure the angular momenta of spin-1/2 particles. These measurements induce a back-action on the reference which is the central focus of our study. We begin by deriving explicit expressions for the quantum channel representing the back-action. Then, we analyze the dynamics incurred by the reference when it is used to sequentially measure particles drawn from a fixed ensemble. We prove that the reference thermalizes with the measured particles and find that generically, the thermal state is reached in time which scales linearly with the size of the reference. This contrasts a recent conclusion of Bartlett et al.\ that this takes a quadratic amount of time when the particles are completely unpolarized. We now understand their result in terms of a simple physical principle based on symmetries and conservation laws. Finally, we initiate the study of the non-equilibrium dynamics of the reference. Here we find that a reference in a coherent state will essentially remain in one when measuring polarized particles, while rotating itself to ultimately align with the polarization of the particles.10aReference frame1 aPoulin, D1 aYard, J uhttps://www.physique.usherbrooke.ca/pages/en/node/621701093nas a2200181 4500008004100000245003800041210003800079300000800117490000600125520063100131653002100762653000900783100001500792700001600807700001400823700001500837856005900852 2006 eng d00aOperator quantum error correction0 aOperator quantum error correction a3820 v63 aThis paper is an expanded and more detailed version of the work \cite{KLP04} in which the Operator Quantum Error Correction formalism was introduced. This is a new scheme for the error correction of quantum operations that incorporates the known techniques –- i.e. the standard error correction model, the method of decoherence-free subspaces, and the noiseless subsystem method –- as special cases, and relies on a generalized mathematical framework for noiseless subsystems that applies to arbitrary quantum operations. We also discuss a number of examples and introduce the notion of ``unitarily noiseless subsystems''.10aError correction10aOQEC1 aKribs, D W1 aLaflamme, R1 aPoulin, D1 aLesosky, M uhttps://www.physique.usherbrooke.ca/pages/en/node/622801482nas a2200133 4500008004100000245007100041210006900112300001100181490000700192520105500199653002101254100001401275856005901289 2006 eng d00aOptimal and Efficient Decoding of Concatenated Quantum Block Codes0 aOptimal and Efficient Decoding of Concatenated Quantum Block Cod a0523330 v743 aWe consider the problem of optimally decoding a quantum error correction code –- that is to find the optimal recovery procedure given the outcomes of partial ``check" measurements on the system. In general, this problem is NP-hard. However, we demonstrate that for concatenated block codes, the optimal decoding can be efficiently computed using a message passing algorithm. We compare the performance of the message passing algorithm to that of the widespread blockwise hard decoding technique. Our Monte Carlo results using the 5 qubit and Steane's code on a depolarizing channel demonstrate significant advantages of the message passing algorithms in two respects. 1) Optimal decoding increases by as much as 94% the error threshold below which the error correction procedure can be used to reliably send information over a noisy channel. 2) For noise levels below these thresholds, the probability of error after optimal decoding is suppressed at a significantly higher rate, leading to a substantial reduction of the error correction overhead.10aError correction1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/621600771nas a2200181 4500008004100000245004700041210004700088300000800135490000600143520028300149653001600432653001200448653001900460653002000479100001700499700001400516856005900530 2006 eng d00aRelational time for systems of oscillators0 aRelational time for systems of oscillators a1510 v43 aUsing an elementary example based on two simple harmonic oscillators, we show how a relational time may be defined that leads to an approximate Schrödinger dynamics for subsystems, with corrections leading to an intrinsic decoherence in the energy eigenstates of the subsystem.10aFoundations10aGravity10aQuantum Theory10aReference frame1 aMilburn, G J1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/622502155nas a2200181 4500008004100000245006100041210006100102300000900163490000700172520163800179653001601817653001201833653001601845653001901861653002001880100001401900856005901914 2006 eng d00aToy model for a relational formulation of quantum theory0 aToy model for a relational formulation of quantum theory a12290 v453 aIn the absence of an external frame of reference –- i.e. in background independent theories such as general relativity –- physical degrees of freedom must describe {\em relations} between systems. Using a simple model, we investigate how such a relational quantum theory naturally arises by promoting reference systems to the status of dynamical entities. Our goal is twofold. First, we demonstrate using elementary quantum theory how any quantum mechanical experiment admits a purely relational description at a fundamental level. Second, we describe how the original ``non-relational" theory approximately emerges from the fully relational theory when reference systems become semi-classical. Our technique is motivated by a Bayesian approach to quantum mechanics, and relies on the noiseless subsystem method of quantum information science used to protect quantum states against undesired noise. The relational theory naturally predicts a fundamental decoherence mechanism, so an arrow of time emerges from a time-symmetric theory. Moreover, our model circumvents the problem of the ``collapse of the wave packet" as the probability interpretation is only ever applied to diagonal density operators. Finally, the physical states of the relational theory can be described in terms of ``spin networks" introduced by Penrose as a combinatorial description of geometry, and widely studied in the loop formulation of quantum gravity. Thus, our simple bottom-up approach (starting from the semi-classical limit to derive the fully relational quantum theory) may offer interesting insights on the low energy limit of quantum gravity.10aFoundations10aGravity10aMeasurement10aQuantum Theory10aReference frame1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/620301309nas a2200205 4500008004100000245009100041210006900132260000800201300001100209490000700220520070800227653001800935653002300953100001400976700001500990700001401005700001901019700001601038856004901054 2005 eng d00aCharacterization of Complex Quantum Dynamics with a Scalable NMR Information Processor0 aCharacterization of Complex Quantum Dynamics with a Scalable NMR bAPS a2505020 v953 aWe present experimental results on the measurement of fidelity decay under contrasting system dynamics using a nuclear magnetic resonance quantum information processor. The measurements were performed by implementing a scalable circuit in the model of deterministic quantum computation with only one quantum bit. The results show measurable differences between regular and complex behaviour and for complex dynamics are faithful to the expected theoretical decay rate. Moreover, we illustrate how the experimental method can be seen as an efficient way for either extracting coarse-grained information about the dynamics of a large system, or measuring the decoherence rate from engineered environments.10aQuantum chaos10aQuantum simulation1 aRyan, C A1 aEmerson, J1 aPoulin, D1 aNegrevergne, C1 aLaflamme, R uhttp://link.aps.org/abstract/PRL/v95/e25050200813nas a2200109 4500008004100000245007500041210006900116520042500185100001400610700002000624856005900644 2005 eng d00aComment on ``Some non-conventional idesa about algorithmic complexity"0 aComment on Some nonconventional idesa about algorithmic complexi3 aWe comment on a recent paper by D'Abramo [Chaos, Solitons & Fractals, 25 (2005) 29], focusing on the author's statement that an algorithm can produce a list of strings containing at least one string whose algorithmic complexity is greater than that of the entire list. We show that this statement, although perplexing, is not as paradoxical as it seems when the definition of algorithmic complexity is applied correctly.1 aPoulin, D1 aTouchette, Hugo uhttps://www.physique.usherbrooke.ca/pages/en/node/620201862nas a2200181 4500008004100000245009800041210006900139300001100208490000700219520131200226653001601538653001601554653001901570100001601589700001401605700001501619856004601634 2005 eng d00aEnvironment as a Witness: Selective Proliferation of Information and Emergence of Objectivity0 aEnvironment as a Witness Selective Proliferation of Information a0421130 v723 aWe study the role of the information deposited in the environment of an open quantum system in course of the decoherence process. Redundant spreading of information –- the fact that some observables of the system can be independently ``read-off'' from many distinct fragments of the environment –- is investigated as the key to effective objectivity, the essential ingredient of ``classical reality''. This focus on the environment as a communication channel through which observers learn about physical systems underscores importance of quantum Darwinism –- selective proliferation of information about ``the fittest states'' chosen by the dynamics of decoherence at the expense of their superpositions –- as redundancy imposes the existence of preferred observables. We demonstrate that the only observables that can leave multiple imprints in the environment are the familiar pointer observables singled out by environment-induced superselection (einselection) for their predictability. Many independent observers monitoring the environment will therefore agree on properties of the system as they can only learn about preferred observables. In this operational sense, the selective spreading of information leads to appearance of an objective ``classical reality'' from within quantum substrate.10aDecoherence10aFoundations10aQuantum Theory1 aOllivier, H1 aPoulin, D1 aZurek, W H uhttp://www.arxiv.org/abs/quant-ph/040812501610nas a2200181 4500008004100000245002800041210002800069300001000097490000700107520115700114653001601271653001301287653001601300653001901316653002001335100001401355856005901369 2005 eng d00aMacroscopic Observables0 aMacroscopic Observables a221020 v713 aWe study macroscopic observables defined as the total value of a physical quantity over a collection of quantum systems. We show that previous results obtained for infinite ensemble of identically prepared systems lead to incorrect conclusions for finite ensembles. In particular, exact measurement of a macroscopic observable significantly disturbs the state of any finite ensemble. However, we show how this disturbance can be made arbitrarily small when the measurement are of finite accuracy. We demonstrate a general tradeoff between state disturbance and measurement coarseness as a function of the size of the ensemble. Using this tradeoff, we show that the histories generated by any sequence of finite accuracy macroscopic measurements always generate a consistent family in the absence of large scale entanglement, for sufficiently large ensembles. Hence, macroscopic observables behave ``classically" provided that their accuracy is coarser than the quantum correlation length-scale of the system. The role of these observable is also discussed in the context of NMR quantum information processing and bulk ensemble quantum state tomography.10aDecoherence10aEmergent10aFoundations10aQuantum Theory10aRenormalization1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/621401391nas a2200145 4500008004100000245006300041210006300104300001100167490000700178520095700185653002101142653000901163100001401172856005901186 2005 eng d00aStabilizer formalism for operator quantum error correction0 aStabilizer formalism for operator quantum error correction a2305040 v953 aOperator quantum error correction is a recently developed theory that provides a generalized framework for active error correction and passive error avoiding schemes. In this paper, we describe these codes in the stabilizer formalism of standard quantum error correction theory. This is achieved by adding a ``gauge" group to the standard stabilizer definition of a code that defines an equivalence class between encoded states. Gauge transformations leave the encoded information unchanged; their effect is absorbed by virtual gauge qubits that do not carry useful information. We illustrate the construction by identifying a gauge symmetry in Shor's 9-qubit code that allows us to remove 4 of its 8 stabilizer generators, leading to a simpler decoding procedure and a wider class of logical operations without affecting its essential properties. This opens the path to possible improvements of the error threshold of fault-tolerant quantum computing.10aError correction10aOQEC1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/621501168nas a2200169 4500008004100000245006700041210006500108300001100173490000700184520067500191653002100866653000900887100001300896700001600909700001400925856005900939 2005 eng d00aA Unified and Generalized Approach to Quantum Error Correction0 aUnified and Generalized Approach to Quantum Error Correction a1805010 v943 aWe present a unified approach to quantum error correction, called operator quantum error correction. Our scheme relies on a generalized notion of noiseless subsystem that is investigated here. By combining active error correction with this generalized noiseless subsystems method, we arrive at the unified approach which incorporates the known techniques –- i.e. the standard error correction model, the method of decoherence-free subspaces, and the noiseless subsystem method –- as special cases. Moreover, we demonstrate that the quantum error correction condition from the standard model is a necessary condition for all known methods of quantum error correction.10aError correction10aOQEC1 aKribs, D1 aLaflamme, R1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/622901229nas a2200181 4500008004100000245006800041210006800109300001100177490000700188520069800195653001800893653002300911100001500934700001300949700001400962700001200976856005900988 2004 eng d00aEstimation of the Local Density of States on a Quantum Computer0 aEstimation of the Local Density of States on a Quantum Computer a0503050 v693 aWe report an efficient quantum algorithm for estimating the local density of states (LDOS) on a quantum computer. The LDOS describes the redistribution of energy levels of a quantum system under the influence of a perturbation. Sometimes known as the ``strength function'' from nuclear spectroscopy experiments, the shape of the LDOS is directly related to the survivial probability of unperturbed eigenstates, and has recently been related to the fidelity decay (or ``Loschmidt echo'') under imperfect motion-reversal. For quantum systems that can be simulated efficiently on a quantum computer, the LDOS estimation algorithm enables an exponential speed-up over direct classical computation.10aQuantum chaos10aQuantum simulation1 aEmerson, J1 aLloyd, S1 aPoulin, D1 aCory, D uhttps://www.physique.usherbrooke.ca/pages/en/node/623301165nas a2200181 4500008004100000245010300041210006900144300001100213490000700224520058600231653001800817653002300835100001400858700002000872700001600892700001600908856005900924 2004 eng d00aExponential Speedup with a Single Bit of Quantum Information: Measuring the Average Fidelity Decay0 aExponential Speedup with a Single Bit of Quantum Information Mea a1779060 v923 aWe present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation, so for those maps admitting an efficient gate decomposition, it provides an exponential speed up over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of eigenvector statistics. Our result also illustrates the role of chaos in the process of decoherence.10aQuantum chaos10aQuantum simulation1 aPoulin, D1 aBlume-Kohout, R1 aLaflamme, R1 aOllivier, H uhttps://www.physique.usherbrooke.ca/pages/en/node/621301084nas a2200145 4500008004100000245008800041210006900129520059700198653002100795100001800816700001500834700001600849700001400865856005900879 2004 eng d00aNoiseless subsystems for collective rotation channels in quantum information theory0 aNoiseless subsystems for collective rotation channels in quantum3 aCollective rotation channels are a fundamental class of channels in quantum computing and quantum information theory. The commutant of the noise operators for such a channel is a c*-algebra which is equal to the set of fixed points for the channel. Finding the precise spatial structure of the commutant algebra for a set of noise operators associated with a channel is a core problem in quantum error prevention. We draw on methods of operator algebras, quantum mechanics and combinatorics to explicitly determine the structure of the commutant for the class of collective rotation channels.10aError correction1 aHolbrook, J A1 aKribs, D W1 aLaflamme, R1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/623001380nas a2200181 4500008004100000245008200041210006900123300001100192490000700203520083300210653001601043653001601059653001901075100001601094700001401110700001501124856005901139 2004 eng d00aObjective properties from subjective quantum states: Environment as a witness0 aObjective properties from subjective quantum states Environment a2204010 v933 aWe study the emergence of objective properties in open quantum systems. In our analysis, the environment is promoted from a passive role of reservoir selectively destroying quantum coherence, to an active role of amplifier selectively proliferating information about the system. We show that only preferred pointer states of the system can leave a redundant and therefore easily detectable imprint on the environment. Observers who–-as it is almost always the case–-discover the state of the system indirectly (by probing a fraction of its environment) will find out only about the corresponding pointer observable. Many observers can act in this fashion independently and without perturbing the system: they will agree about the state of the system. In this operational sense, em preferred pointer states exist objectively.10aDecoherence10aFoundations10aQuantum Theory1 aOllivier, H1 aPoulin, D1 aZurek, W H uhttps://www.physique.usherbrooke.ca/pages/en/node/622101350nas a2200193 4500008004100000245008700041210006900128300001100197490000700208520076700215653001100982653002100993100001801014700001701032700001601049700001401065700001801079856005901097 2004 eng d00aRobust Polarization-Based Quantum Key Distribution over a Collective-Noise Channel0 aRobust PolarizationBased Quantum Key Distribution over a Collect a0179010 v923 aWe present two polarization-based protocols for quantum key distribution. The protocols encode key bits in noiseless subspaces or subsystems, and so can function over a quantum channel subjected to an arbitrary degree of collective noise, as occurs, for instance, due to rotation of polarizations in an optical fiber. These protocols can be implemented using only entangled photon-pair sources, single-photon rotations, and single-photon detectors. Thus, our proposals offer practical and realistic alternatives to existing schemes for quantum key distribution over optical fibers without resorting to interferometry or two-way quantum communication, thereby circumventing, respectively, the need for high precision timing and the threat of Trojan horse attacks.10aCrypto10aError correction1 aBoileau, J -C1 aGottesman, D1 aLaflamme, R1 aPoulin, D1 aSpekkens, R W uhttps://www.physique.usherbrooke.ca/pages/en/node/623801308nas a2200193 4500008004100000245008500041210006900126300001100195490000700206520072500213653002100938653001400959653001500973100001300988700001601001700001401017700002401031856005901055 2003 eng d00aComment on 'Absence of a Slater Transition in the Two-Dimensional Hubbard Model'0 aComment on Absence of a Slater Transition in the TwoDimensional a0997020 v903 a{In a recent paper, Physical Review Letters 87, 167010/1-4 (2001), Moukouri and Jarrell presented evidence that in the two-dimensional (d=2) Hubbard model at half-filling there is a metal-insulator transition (MIT) at finite temperature even in weak coupling. While we agree with the numerical results of that paper, we arrive at different conclusions: The apparent gap at finite-temperature can be understood, at weak-coupling, as a crossover phenomenon involving large (but not infinite) antiferromagnetic (AFM) correlation length. Phase-space effects on the self-energy in d=2 are crucial, as are the ratio between AFM correlation length and single-particle thermal de Broglie wavelength. In weak coupling

10aCondensed matter10aMany-Body10aSimulation1 aKyung, B1 aLandry, J S1 aPoulin, D1 aTremblay, A.-M., S. uhttps://www.physique.usherbrooke.ca/pages/en/node/622700753nas a2200145 4500008004100000245003600041210003600077300001400113490000700127520036400134653001600498100001400514700002000528856005900548 2003 eng d00aCompatibility of quantum states0 aCompatibility of quantum states a010101(R)0 v673 aWe introduce a measure of the compatibility between quantum states–-the likelihood that two density matrices describe the same object. Our measure is motivated by two elementary requirements, which lead to a natural definition. We list some properties of this measure, and discuss its relation to the problem of combining two observers' states of knowledge.10aFoundations1 aPoulin, D1 aBlume-Kohout, R uhttps://www.physique.usherbrooke.ca/pages/en/node/621101001nas a2200181 4500008004100000245006800041210006800109300001100177490000700188520046300195653001800658653002300676100001400699700001600713700001700729700001400746856005900760 2003 eng d00aTesting Intergrability with a single bit of quantum information0 aTesting Intergrability with a single bit of quantum information a0223020 v683 aWe show that deterministic quantum computing with a single bit (DQC1) can determine whether the classical limit of a quantum system is chaotic or integrable using $O(N)$ physical resources, where $N$ is the dimension of the Hilbert space of the system under study. This is a square root improvement over all known classical procedures. Our study relies strictly on the random matrix conjecture. We also present numerical results for the nonlinear kicked top.10aQuantum chaos10aQuantum simulation1 aPoulin, D1 aLaflamme, R1 aMilburn, G J1 aPaz, J -P uhttps://www.physique.usherbrooke.ca/pages/en/node/621201023nas a2200109 4500008004100000245003500041210003300076520071300109653001800822100001400840856005900854 2002 eng d00aA rough guide to quantum chaos0 arough guide to quantum chaos3 aThis tutorial offers some insight into the question ``What is quantum chaos and why is it interesting?''. Its main purpose is to present some signatures of chaos in the quantum world. This is ıt not} a technical reference, it contains but a few simple equations and no explicit references; rather, the main body of this manuscript is followed by a reading guide. Some of the mathematical tools used in the field are so cumbersome they often obscure the physical relevance of the problem under investigation. However, after having consulted this tutorial, the technical literature should appear less mysterious and, we hope, one should have a better intuition of what is interesting, and what is superficial!10aQuantum chaos1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/620101016nas a2200133 4500008004100000245005100041210005100092300001000143490000700153520063300160653001600793100001400809856005900823 2001 eng d00aClassicality of Quantum Information Processing0 aClassicality of Quantum Information Processing a423190 v653 aThe ultimate goal of the classicality program is to quantify the amount of quantumness of certain processes. Here, classicality is studied for a restricted type of process: quantum information processing (QIP). Under special conditions, one can force some qubits of a quantum computer into a classical state without affecting the outcome of the computation. The minimal set of conditions is described and its structure is studied. Some implications of this formalism are the increase of noise robustness, a proof of the quantumness of mixed state quantum computing and a step forward in understanding the very foundation of QIP.10aFoundations1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/621002341nas a2200157 4500008004100000245012600041210007100167260003000238520177200268653002102040653001402061653001502075100002002090700001402110856005902124 2000 eng d00aAspects numériques des simulations du modèle de {Hubbard} –- {M}onte {C}arlo quantique et méthode d'entropie maximum0 aAspects numériques des simulations du modèle de Hubbard M onte C bUniversité de Sherbrooke3 aNous présentons dans ce rapport une introduction complète à deux algorithmes couramment utilisés en physique du solide dans le cadre du problème à N-corps quantique. Le premier est l'algorithme de Blankenbecler, Scalapino et Sugar (bss) (aussi appelé algorithme du déterminant), développé au début des années 80 dans le but de calculer numériquement les propriétés thermodynamiques de certains modèles d'électrons fortement corrélés, dont celui de Hubbard, étudié ici comme modèle pour la supraconductivité à haut Tc. Pour cette partie du rapport, notre étude présente d'abord le fonctionnement de l'algorithme pour s'attarder ensuite à certains de ses aspects numériques, en particulier ceux qui sont problématiques au niveau de la stabilité des calculs. Parmi ceux-ci, nous retrouvons les instabilités liées aux calculs à basse température, le choix de la décomposition de Trotter, le calcul des fonctions de Green et des observables à temps inégal, de même que le problème d'ergodicité. En deuxième partie, nous abordons le calcul des propriétés dynamiques du modèle de Hubbard, comme le poids spectral obtenu en prolongeant analytiquement les données Monte Carlo calculées en temps imaginaire. Pour cette section du rapport, nous présentons quelques éléments de la théorie de la régularisation et la méthode d'entropie maximum utilisés pour résoudre le problème numériquement mal posé que constitue le prolongement analytique des données Monte Carlo. Finalement, pour rendre ce rapport complet en soi, nous avons inclut en annexe une introduction à quelques outils d'analyse numérique ainsi qu'un guide de lecture renvoyant à des références de base sur la plupart des sujets traités dans ce rapport.10aCondensed matter10aMany-Body10aSimulation1 aTouchette, Hugo1 aPoulin, D uhttps://www.physique.usherbrooke.ca/pages/en/node/619801487nas a2200229 4500008004100000245007900041210006900120300001600189490000700205520082900212653002101041653001401062653001501076100001601091700001301107700001301120700001301133700001401146700001401160700002401174856005901198 2000 eng d00aMany-body theory versus simulations for the pseudogap in the Hubbard model0 aManybody theory versus simulations for the pseudogap in the Hubb a7887–78920 v613 aThe opening of a critical-fluctuation-induced pseudogap (or precursor pseudogap) in the one-particle spectral weight of the half-filled two-dimensional Hubbard model is discussed. This pseudogap, appearing in our Monte Carlo simulations, may be obtained from many-body techniques that use Green functions and vertex corrections that are at the same level of approximation. Self-consistent theories of the Eliashberg type (such as the fluctuation exchange approximation) use renormalized Green functions and bare vertices in a context where there is no Migdal theorem. They do not find the pseudogap, in quantitative and qualitative disagreement with simulations, suggesting these methods are inadequate for this problem. Differences between precursor pseudogaps and strong-coupling pseudogaps are also discussed.

10aCondensed matter10aMany-Body10aSimulation1 aMoukouri, S1 aAllen, S1 aLemay, F1 aKyung, B1 aPoulin, D1 aVilk, Y M1 aTremblay, A.-M., S. uhttps://www.physique.usherbrooke.ca/pages/en/node/6224