Équipe

Chercheurs

Vincent Aimez

Yves BérubéLauzière
 Alexandre Blais

François Boone
 Claude Bourbonnais

Laurent Caron

Serge Charlebois
 René Côté
 Dominique Drouin
 Éva DupontFerrier
 Glen Evenbly
 Patrick Fournier
 Sébastien Gagné
 Ion Garate Aramberri

Max Hofheinz
 Serge Jandl

MarieClaude Michaud
 Denis Morris
 Michel PioroLadrière
 David Poulin

JeanFrançois Pratte
 Jeffrey Quilliam
 Bertrand Reulet
 David Sénéchal

Julien Sylvestre
 Louis Taillefer
 AndréMarie Tremblay

Vincent Aimez

Étudiants
 Mohammad Abbasi Eskandari
 Shaheen Acheche
 Azin Aghdaei
 Arezoo Ahmadi Afshar
 Steve Allen
 Dave Allen
 Ataei Amirreza
 Andrew Argouin
 LouisFrançois Arsenault
 GetenetTesega Ayele
 Hassan Bakrim
 Xavier BarnabéThériault
 Manuel Barrette
 Félix Beaudoin
 Alexandre Beaudoin
 Mathieu Beauregard
 Alexandre BédardVallée
 Behnaz Behmand
 Pierre Bénard
 Jean Bergeron
 Dominic Bergeron
 Simon Bertrand
 Youcef Ataellah Bioud
 Antoine Blanchette
 Daniel Boies
 Maxime Boissonneault
 Adam Bolduc
 Dorra Bouchiha
 MarieÈve Boulanger
 Vincent Bouliane
 Louis Bourassa
 Jérôme Bourassa
 Benjamin Bourassa
 Patrick BourgeoisHope
 Hugo Bourque
 Samuel Boutin
 Mehdi BozzoRey
 Naima Brahiti
 Simon Branchaud
 Pierre Breton
 Charles Brillon
 Priyanka Brojabasi
 Frédéric Brousseau
 Chloé BureauOxton
 Julien CamirandLemyre
 Maxime Charlebois
 Sophie Charpentier
 Dominique Chassé
 Laurent Chaussé
 Clément Collignon
 Olivier CyrChoinière
 AnneMarie Daré
 Siddartha Dash
 Guillaume Dauphinais
 Gabrielle Denhez
 Aurélie Denoyer
 Agustin Di Paolo
 Adama Moussa Diallo
 Charles Doiron
 Gabriel Droulers
 Guillaume DuclosCianci
 Sophie DufourBeauséjour
 Emmanuel Dupuy
 Maxime DurandGasselin
 Abderrahim El Amrani
 Ghania Farhi
 Alexandre Faribault
 Jean Paul Latyr Faye
 Alexandre Foley
 JeanCharles Forgues
 Bertrand Fourcade
 AnneMarie Gagnon
 Luis Garcia
 Gabriel Gasse
 Jonathan Gaudet
 Louis Gaudreau
 François Gaudreau
 René Gélinas
 Marc Girard
 PhilippeOlivier Giroux
 Maxime Godard
 Sébastien GodinProulx
 MarieÈve Gosselin
 MarieChristine Gosselin
 Elmoez Goubaa
 Jonathan Graveline
 Gaël Grissonnanche
 Daniel Groleau
 Chitov Guennadi
 Mathieu Guillot
 JeanFrançois Guimond
 Louis Haeberle
 Guillaume Hardy
 Nicolas Harnois
 Patrick HarveyCollard
 CharlesDavid Hébert
 Vahid Hemmati
 Samuel Houle
 Pavithran Iyer Sridharan
 Francis Jackson
 JeanFrançois Jobidon
 Defi Junior Jubgang Fandio
 Alexandre JuneauFecteau
 SékouOumar Kaba
 Anirudh Krishna
 Dany Lachance Qurion
 Mathieu Lachapelle
 Vincent Lafage
 Francis Laliberté
 Kevin Lalumière
 Jules Lambert
 Guillaume Lamoureux
 Wangwei Lan
 Olivier LandonCardinal
 Simon Landry
 Alexandre Langlois
 Maxime LapointeMajor
 Samuel Larocque
 Jonathan Laverdière
 David Leboeuf
 Anaëlle Legros
 François Lemay
 Jessica Lemieux
 MarcAntoine Lemonde
 Stéphane Lessard
 Yannick Lévesque
 Maude Lizaire
 Wenchen Luo
 SimonAlexandre Lussier
 Arbi Maalaoui
 Anthoni Manseau
 Dominique Matte
 Moctar Mbodji
 Hosni Meddeb
 Samuel Ménard
 Marc Ménard
 Pierre MercureBoissonnault
 Mouawad Merhej
 François Michaud
 Bastien Michon
 Hugues Nélisse
 Joselyne Nshimirimana
 Laurent Olivier
 Thami Ouahbi
 Alexandre Ouellet
 Stéphane Pairault
 Alexandre Payeur
 Émilie Pelchat
 NathalieEmmanuelle Perret
 Branko Petrov
 Dany Plouffe
 Maxime Plourde
 Gabriel PoulinLamarre
 Aurore Quelennec
 Jorge Eduardo Ramirez Ruiz
 JeanPhilippe Reid
 Jacques Renaud
 Samuel René De Cotret
 Alexis Reymbaut
 JeanPhilippe Richard
 Pierre Rinkel
 Guillaume Roberge
 Serge Robillard
 Sophie Rochette
 Maxime Rondeau
 Redha Rouane
 Alexandre Rousseau
 Sébastien Roy
 AnneMarie Roy
 David RoyGuay
 Baptiste Royer
 Peyman Sahebsara
 Yacoubou Salissou
 Fatou Bintou Sane
 Daniel Sarrazin
 Vincent Sasseville
 Stéphane Savard
 Christian Scheiber
 Elwallid Sedik
 Patrick Semon
 Maryam Shahbazi
 Olivier Simard
 JeanOlivier Simoneau
 Gary Slater
 Kevin Spahr
 Ken StArnaud
 Lucas StJean
 Romain Stricher
 Steven Terranova
 Emannuel Tetsi
 Karl Thibault
 Samuel Tremblay
 Réal Tremblay
 Maxime Tremblay
 Alain Tremblay
 Olesia Tutashkonko
 Quentin Vandier
 Alain Veilleux
 Jonathan Vermette
 Simon Verret
 Aimé Verrier
 Djamel Ziat
 Jihene Zribi

Équipe technique
 Équipe administrative
Chercheurs
David Poulin
Département de physique,
Faculté des sciences
Téléphone : 62054, poste 62054
Courriel : david.poulin@usherbrooke.ca
Site web personnel : http://www.physique.usherbrooke.ca/poulin
Biographie
Sujets de recherche
Informatique quantique, algorithmes quantiques, correction d’erreur quantique, information quantique à Ncorps.
Intérêts de recherche
Je m’intéresse aux questions suivantes : quelles tâches informatiques peuton accomplir plus efficacement en utilisant la mécanique quantique ? Comment réaliser de tels processeurs d’information de façon efficace à partir de dispositifs bruyants ? Quels outils techniques et concepts fondamentaux peuton tirer de l’informatique quantique afin de les appliquer dans d’autres domaines scientifiques ?
Motsclés
Calcul quantique tolérant aux fautes, inférence statistique quantique, ordre topologique, simulations quantiques, théorie de Shannon quantique, ordinateur quantique, communication quantique, réseaux de tenseurs
Publications
2017 
Ferris, Andrew; Hirche, Christoph; Poulin, David Convolutional Polar Codes Divers 2017. @misc{FHP17a, title = {Convolutional Polar Codes}, author = {Andrew Ferris and Christoph Hirche and David Poulin}, year = {2017}, date = {20170101}, abstract = {Arikan's Polar codes attracted much attention as the first efficiently decodable and capacity achieving codes. Furthermore, Polar codes exhibit an exponentially decreasing block error probability with an asymptotic error exponent upper bounded by 1/2. Since their discovery, many attempts have been made to improve the error exponent and the finite blocklength performance, while keeping the blocstructured kernel. Recently, two of us introduced a new family of efficiently decodable errorcorrection codes based on a recently discovered efficientlycontractible tensor network family in quantum manybody physics, called branching MERA. These codes, called branching MERA codes, include Polar codes and also extend them in a nontrivial way by substituting the blocstructured kernel by a convolutional structure. Here, we perform an indepth study of a particular example that can be thought of as a direct extension to Arikan's Polar code, which we therefore name Convolutional Polar codes. We prove that these codes polarize and exponentially suppress the channel's error probability, with an asymptotic error exponent log_2(3)/2 which is provably better than for Polar codes under successive cancellation decoding. We also perform finite blocksize numerical simulations which display improved errorcorrecting capability with only a minor impact on decoding complexity.}, keywords = {}, pubstate = {published}, tppubtype = {misc} } Arikan's Polar codes attracted much attention as the first efficiently decodable and capacity achieving codes. Furthermore, Polar codes exhibit an exponentially decreasing block error probability with an asymptotic error exponent upper bounded by 1/2. Since their discovery, many attempts have been made to improve the error exponent and the finite blocklength performance, while keeping the blocstructured kernel. Recently, two of us introduced a new family of efficiently decodable errorcorrection codes based on a recently discovered efficientlycontractible tensor network family in quantum manybody physics, called branching MERA. These codes, called branching MERA codes, include Polar codes and also extend them in a nontrivial way by substituting the blocstructured kernel by a convolutional structure. Here, we perform an indepth study of a particular example that can be thought of as a direct extension to Arikan's Polar code, which we therefore name Convolutional Polar codes. We prove that these codes polarize and exponentially suppress the channel's error probability, with an asymptotic error exponent log_2(3)/2 which is provably better than for Polar codes under successive cancellation decoding. We also perform finite blocksize numerical simulations which display improved errorcorrecting capability with only a minor impact on decoding complexity. 
Darmawan, Andrew S; Poulin, David Tensornetwork simulations of the surface code under realistic noise Article de journal Phys. Rev. Lett., 119 , p. 040502, 2017. @article{DP16b, title = {Tensornetwork simulations of the surface code under realistic noise}, author = {Andrew S. Darmawan and David Poulin}, year = {2017}, date = {20170101}, journal = {Phys. Rev. Lett.}, volume = {119}, pages = {040502}, abstract = {The surface code is a manybody quantum system, and simulating it in generic conditions is computationally hard. While the surface code is believed to have a high threshold, the numerical simulations used to establish this threshold are based on simplified noise models. We present a tensornetwork algorithm for simulating error correction with the surface code under arbitrary local noise. Our simulation is exact within statistical fluctuations and we use it to study the threshold and the subthreshold behaviour of the amplitudedamping and systematic rotation channels. We also compare these exact results to those obtained by making standard approximations to the noise models.}, keywords = {}, pubstate = {published}, tppubtype = {article} } The surface code is a manybody quantum system, and simulating it in generic conditions is computationally hard. While the surface code is believed to have a high threshold, the numerical simulations used to establish this threshold are based on simplified noise models. We present a tensornetwork algorithm for simulating error correction with the surface code under arbitrary local noise. Our simulation is exact within statistical fluctuations and we use it to study the threshold and the subthreshold behaviour of the amplitudedamping and systematic rotation channels. We also compare these exact results to those obtained by making standard approximations to the noise models. 
Chamberland, Christopher; Iyer, Pavithran; Poulin, David FaultTolerant Quantum Computing in the Pauli or Clifford Frame with Slow Error Diagnostics Divers 2017. @misc{CIP17a, title = {FaultTolerant Quantum Computing in the Pauli or Clifford Frame with Slow Error Diagnostics}, author = {Christopher Chamberland and Pavithran Iyer and David Poulin}, year = {2017}, date = {20170101}, keywords = {}, pubstate = {published}, tppubtype = {misc} } 
Dauphinais, Guillaume; Poulin, David FaultTolerant Quantum Error Correction for nonAbelian Anyons Article de journal Comm. Math. Phys., 355 , p. 519, 2017. @article{DP16a, title = {FaultTolerant Quantum Error Correction for nonAbelian Anyons}, author = {Guillaume Dauphinais and David Poulin}, year = {2017}, date = {20170101}, journal = {Comm. Math. Phys.}, volume = {355}, pages = {519}, abstract = {While topological quantum computation is intrinsically faulttolerant at zero temperature, it looses its topological protection at any finite temperature. We present a scheme to protect the information stored in a system supporting noncyclic anyons against thermal and measurement errors. The correction procedure builds on the work of Gács citeGacs_86 and Harrington citeHarrington_04 and operates as a local cellular automaton. In contrast to previously studied schemes, our scheme is valid for both abelian and nonabelian anyons and accounts for measurement errors. We prove the existence of a faulttolerant threshold and numerically simulate the procedure for a system of Ising anyons. The result of our simulations are consistent with a threshold between $10^4$ and $10^3$.}, keywords = {}, pubstate = {published}, tppubtype = {article} } While topological quantum computation is intrinsically faulttolerant at zero temperature, it looses its topological protection at any finite temperature. We present a scheme to protect the information stored in a system supporting noncyclic anyons against thermal and measurement errors. The correction procedure builds on the work of Gács citeGacs_86 and Harrington citeHarrington_04 and operates as a local cellular automaton. In contrast to previously studied schemes, our scheme is valid for both abelian and nonabelian anyons and accounts for measurement errors. We prove the existence of a faulttolerant threshold and numerically simulate the procedure for a system of Ising anyons. The result of our simulations are consistent with a threshold between $10^4$ and $10^3$. 
Haah, Jeongwan; Hastings, Matthew B; Poulin, David; Wecker, Dave Magic state distillation with low space overhead and optimal asymptotic input count Divers 2017. @misc{HHPW17a, title = {Magic state distillation with low space overhead and optimal asymptotic input count}, author = {Jeongwan Haah and Matthew B. Hastings and David Poulin and Dave Wecker}, year = {2017}, date = {20170101}, keywords = {}, pubstate = {published}, tppubtype = {misc} } 
Haah, Jeongwan; Hastings, Matthew B; Poulin, David; Wecker, Dave Magic State Distillation at Intermediate Size Divers 2017. @misc{HHPW17b, title = {Magic State Distillation at Intermediate Size}, author = {Jeongwan Haah and Matthew B. Hastings and David Poulin and Dave Wecker}, year = {2017}, date = {20170101}, abstract = {Recently we proposed a family of magic state distillation protocols that obtains asymptotic performance that is conjectured to be optimal. This family depends upon several codes, called "inner codes" and öuter codes." We presented some small examples of these codes as well as an analysis of codes in the asymptotic limit. Here, we analyze such protocols in an intermediate size regime, using hundreds to thousands of qubits. We use BCH inner codes, combined with various outer codes. We extend our protocols by adding error correction in some cases. We present a variety of protocols in various input error regimes; in many cases these protocols require significantly fewer input magic states to obtain a given output error than previous protocols.}, keywords = {}, pubstate = {published}, tppubtype = {misc} } Recently we proposed a family of magic state distillation protocols that obtains asymptotic performance that is conjectured to be optimal. This family depends upon several codes, called "inner codes" and öuter codes." We presented some small examples of these codes as well as an analysis of codes in the asymptotic limit. Here, we analyze such protocols in an intermediate size regime, using hundreds to thousands of qubits. We use BCH inner codes, combined with various outer codes. We extend our protocols by adding error correction in some cases. We present a variety of protocols in various input error regimes; in many cases these protocols require significantly fewer input magic states to obtain a given output error than previous protocols. 
2016 
Jacob C. Bridgeman, Steven Flammia T; Poulin, David Detecting Topological Order with Ribbon Operators Article de journal Phys. Rev. B, 94 , p. 205123, 2016. @article{BFP16a, title = {Detecting Topological Order with Ribbon Operators}, author = {Jacob C. Bridgeman, Steven T. Flammia and David Poulin}, year = {2016}, date = {20160101}, journal = {Phys. Rev. B}, volume = {94}, pages = {205123}, abstract = {We introduce a numerical method for identifying topological order in twodimensional models based on onedimensional bulk operators. The idea is to identify approximate symmetries supported on thin strips through the bulk that behave as string operators associated to an anyon model. We can express these ribbon operators in matrix product form and define a cost function that allows us to efficiently optimize over this ansatz class. We test this method on spin models with abelian topological order by finding ribbon operators for ℤd quantum double models with local fields and Isinglike terms. In addition, we identify ribbons in the abelian phase of Kitaev's honeycomb model which serve as the logical operators of the encoded qubit for the quantum errorcorrecting code. We further identify the topologically encoded qubit in the quantum compass model, and show that despite this qubit, the model does not support topological order. Finally, we discuss how the method supports generalizations for detecting nonabelian topological order.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We introduce a numerical method for identifying topological order in twodimensional models based on onedimensional bulk operators. The idea is to identify approximate symmetries supported on thin strips through the bulk that behave as string operators associated to an anyon model. We can express these ribbon operators in matrix product form and define a cost function that allows us to efficiently optimize over this ansatz class. We test this method on spin models with abelian topological order by finding ribbon operators for ℤd quantum double models with local fields and Isinglike terms. In addition, we identify ribbons in the abelian phase of Kitaev's honeycomb model which serve as the logical operators of the encoded qubit for the quantum errorcorrecting code. We further identify the topologically encoded qubit in the quantum compass model, and show that despite this qubit, the model does not support topological order. Finally, we discuss how the method supports generalizations for detecting nonabelian topological order. 
Nicolas Delfosse, Pavithran Iyer ; Poulin, David Generalized surface codes and packing of logical qubits Divers 2016. @misc{DIP16a, title = {Generalized surface codes and packing of logical qubits}, author = {Nicolas Delfosse, Pavithran Iyer and David Poulin}, year = {2016}, date = {20160101}, abstract = {We consider a notion of relative homology (and cohomology) for surfaces with two types of boundaries. Using this tool, we study a generalization of Kitaev's code based on surfaces with mixed boundaries. This construction includes both Bravyi and Kitaev's and Freedman and Meyer's extension of Kitaev's toric code. We argue that our generalization offers a denser storage of quantum information. In a planar architecture, we obtain a threefold overhead reduction over the standard architecture consisting of a punctured square lattice.}, keywords = {}, pubstate = {published}, tppubtype = {misc} } We consider a notion of relative homology (and cohomology) for surfaces with two types of boundaries. Using this tool, we study a generalization of Kitaev's code based on surfaces with mixed boundaries. This construction includes both Bravyi and Kitaev's and Freedman and Meyer's extension of Kitaev's toric code. We argue that our generalization offers a denser storage of quantum information. In a planar architecture, we obtain a threefold overhead reduction over the standard architecture consisting of a punctured square lattice. 
Nicolas Delfosse, Pavithran Iyer ; Poulin, David A lineartime benchmarking tool for generalized surface codes Divers 2016. @misc{DIP16b, title = {A lineartime benchmarking tool for generalized surface codes}, author = {Nicolas Delfosse, Pavithran Iyer and David Poulin}, year = {2016}, date = {20160101}, abstract = {Quantum information processors need to be protected against errors and faults. One of the most widely considered faulttolerant architecture is based on surface codes. While the general principles of these codes are well understood and basic code properties such as minimum distance and rate are easy to characterize, a code's average performance depends on the detailed geometric layout of the qubits. To date, optimizing a surface code architecture and comparing different geometric layouts relies on costly numerical simulations. Here, we propose a benchmarking algorithm for simulating the performance of surface codes, and generalizations thereof, that runs in linear time. We implemented this algorithm in a software that generates performance reports and allows to quickly compare different architectures.}, keywords = {}, pubstate = {published}, tppubtype = {misc} } Quantum information processors need to be protected against errors and faults. One of the most widely considered faulttolerant architecture is based on surface codes. While the general principles of these codes are well understood and basic code properties such as minimum distance and rate are easy to characterize, a code's average performance depends on the detailed geometric layout of the qubits. To date, optimizing a surface code architecture and comparing different geometric layouts relies on costly numerical simulations. Here, we propose a benchmarking algorithm for simulating the performance of surface codes, and generalizations thereof, that runs in linear time. We implemented this algorithm in a software that generates performance reports and allows to quickly compare different architectures. 
2015 
DuclosCianci, G; Poulin, D Reducing the quantum computing overhead with complex gate distillation Article de journal Phys. Rev. A, 91 , p. 042315, 2015. @article{DP14a, title = {Reducing the quantum computing overhead with complex gate distillation}, author = {G. DuclosCianci and D. Poulin}, year = {2015}, date = {20150101}, journal = {Phys. Rev. A}, volume = {91}, pages = {042315}, abstract = {In leading faulttolerant quantum computing schemes, accurate transformation are obtained by a twostage process. In a first stage, a discrete, universal set of faulttolerant operations is obtained by errorcorrecting noisy transformations and distilling resource states. In a second stage, arbitrary transformations are synthesized to desired accuracy by combining elements of this set into a circuit. Here, we present a scheme which merges these two stages into a single one, directly distilling complex transformations. We find that our scheme can reduce the total overhead to realize certain gates by up to a few orders of magnitude. In contrast to other schemes, this efficient gate synthesis does not require computationally intensive compilation algorithms, and a straightforward generalization of our scheme circumvents compilation and synthesis altogether.}, keywords = {}, pubstate = {published}, tppubtype = {article} } In leading faulttolerant quantum computing schemes, accurate transformation are obtained by a twostage process. In a first stage, a discrete, universal set of faulttolerant operations is obtained by errorcorrecting noisy transformations and distilling resource states. In a second stage, arbitrary transformations are synthesized to desired accuracy by combining elements of this set into a circuit. Here, we present a scheme which merges these two stages into a single one, directly distilling complex transformations. We find that our scheme can reduce the total overhead to realize certain gates by up to a few orders of magnitude. In contrast to other schemes, this efficient gate synthesis does not require computationally intensive compilation algorithms, and a straightforward generalization of our scheme circumvents compilation and synthesis altogether. 
Iyer, Pavithran ; Poulin, David Hardness of decoding quantum stabilizer codes Article de journal IEEE Trans. Info. Theor., 61 , p. 5209, 2015. @article{IP13a, title = {Hardness of decoding quantum stabilizer codes}, author = {Iyer, Pavithran and Poulin, David}, year = {2015}, date = {20150101}, journal = {IEEE Trans. Info. Theor.}, volume = {61}, pages = {5209}, abstract = {In this article we address the computational hardness of optimally decoding a quantum stabilizer code. Much like classical linear codes, errors are detected by measuring certain check operators which yield an error syndrome, and the decoding problem consists of determining the most likely recovery given the syndrome. The corresponding classical problem is known to be NPcomplete, and a similar decoding problem for quantum codes is also known to be NPcomplete. However, this decoding strategy is not optimal in the quantum setting as it does not take into account error degeneracy, which causes distinct errors to have the same effect on the code. Here, we show that optimal decoding of stabilizer codes is computationally much harder than optimal decoding of classical linear codes, it is #P.}, keywords = {}, pubstate = {published}, tppubtype = {article} } In this article we address the computational hardness of optimally decoding a quantum stabilizer code. Much like classical linear codes, errors are detected by measuring certain check operators which yield an error syndrome, and the decoding problem consists of determining the most likely recovery given the syndrome. The corresponding classical problem is known to be NPcomplete, and a similar decoding problem for quantum codes is also known to be NPcomplete. However, this decoding strategy is not optimal in the quantum setting as it does not take into account error degeneracy, which causes distinct errors to have the same effect on the code. Here, we show that optimal decoding of stabilizer codes is computationally much harder than optimal decoding of classical linear codes, it is #P. 
Olivier LandonCardinal Beni Yoshida, John Preskill ; Poulin, David Perturbative instability of quantum memory based on effective longrange interactions Divers 2015. @misc{LYPP15a, title = {Perturbative instability of quantum memory based on effective longrange interactions}, author = {Olivier LandonCardinal, Beni Yoshida, John Preskill and David Poulin}, year = {2015}, date = {20150101}, journal = {Phys. Rev. A}, volume = {91}, pages = {032303}, keywords = {}, pubstate = {published}, tppubtype = {misc} } 
Paul Webster, Stephen Bartlett D; Poulin, David Reducing the overhead for quantum computation when noise is biased Divers 2015. @misc{WBP15a, title = {Reducing the overhead for quantum computation when noise is biased}, author = {Paul Webster, Stephen D. Bartlett and David Poulin}, year = {2015}, date = {20150101}, journal = {Phys. Rev. A}, volume = {92}, pages = {062309}, abstract = {We analyse a model for faulttolerant quantum computation with low overhead suitable for situations where the noise is biased. The basis for this scheme is a gadget for the faulttolerant preparation of magic states that enable universal faulttolerant quantum computation using only Clifford gates that preserve the noise bias. We analyse the distillation of T⟩type magic states using this gadget at the physical level, followed by concatenation with the 15qubit quantum ReedMuller code, and comparing our results with standard constructions. In the regime where the noise bias (rate of Pauli Z errors relative to other singlequbit errors) is greater than a factor of 10, our scheme has lower overhead across a broad range of relevant noise rates.}, keywords = {}, pubstate = {published}, tppubtype = {misc} } We analyse a model for faulttolerant quantum computation with low overhead suitable for situations where the noise is biased. The basis for this scheme is a gadget for the faulttolerant preparation of magic states that enable universal faulttolerant quantum computation using only Clifford gates that preserve the noise bias. We analyse the distillation of T⟩type magic states using this gadget at the physical level, followed by concatenation with the 15qubit quantum ReedMuller code, and comparing our results with standard constructions. In the regime where the noise bias (rate of Pauli Z errors relative to other singlequbit errors) is greater than a factor of 10, our scheme has lower overhead across a broad range of relevant noise rates. 
2014 
Anderson, Jonas T; DuclosCianci, Guillaume ; Poulin, David Faulttolerant conversion between the Steane and ReedMuller quantum codes Article de journal Phys. Rev. Lett., 113 , p. 080501, 2014. @article{ADP14a, title = {Faulttolerant conversion between the Steane and ReedMuller quantum codes}, author = {Anderson, Jonas T. and DuclosCianci, Guillaume and Poulin, David}, year = {2014}, date = {20140101}, journal = {Phys. Rev. Lett.}, volume = {113}, pages = {080501}, abstract = {Steane's 7qubit quantum errorcorrecting code admits a set of faulttolerant gates that generate the Clifford group, which in itself is not universal for quantum computation. The 15qubit ReedMuller code also does not admit a universal faulttolerant gate set but possesses faulttolerant T and controlcontrolZ gates. Combined with the Clifford group, either of these two gates generate a universal set. Here, we combine these two features by demonstrating how to faulttolerantly convert between these two codes, providing a new method to realize universal faulttolerant quantum computation. One interpretation of our result is that both codes correspond to the same subsystem code in different gauges. Our scheme extends to the entire family of quantum ReedMuller codes.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Steane's 7qubit quantum errorcorrecting code admits a set of faulttolerant gates that generate the Clifford group, which in itself is not universal for quantum computation. The 15qubit ReedMuller code also does not admit a universal faulttolerant gate set but possesses faulttolerant T and controlcontrolZ gates. Combined with the Clifford group, either of these two gates generate a universal set. Here, we combine these two features by demonstrating how to faulttolerantly convert between these two codes, providing a new method to realize universal faulttolerant quantum computation. One interpretation of our result is that both codes correspond to the same subsystem code in different gauges. Our scheme extends to the entire family of quantum ReedMuller codes. 
Ferris, Andrew; Poulin, David Branching MERA codes: a natural extension of classical and quantum polar codes Inproceedings International Symposium on Information Theory, IEEE 2014. @inproceedings{FP14a, title = {Branching MERA codes: a natural extension of classical and quantum polar codes}, author = {Andrew Ferris and David Poulin}, year = {2014}, date = {20140101}, booktitle = {International Symposium on Information Theory}, organization = {IEEE}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 
Ferris, Andrew J; Poulin, David Tensor Networks and Quantum Error Correction Article de journal Phys. Rev. Lett., 113 , p. 030501, 2014. @article{FP14d, title = {Tensor Networks and Quantum Error Correction}, author = {Ferris, Andrew J. and Poulin, David}, year = {2014}, date = {20140101}, journal = {Phys. Rev. Lett.}, volume = {113}, pages = {030501}, abstract = {We establish several relations between quantum error correction (QEC) and tensor network (TN) methods of quantum manybody physics. We exhibit correspondences between wellknown families of QEC codes and TNs, and demonstrate a formal equivalence between decoding a QEC code and contracting a TN. We build on this equivalence to propose a new family of quantum codes and decoding algorithms that generalize and improve upon quantum polar codes and successive cancellation decoding in a natural way.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We establish several relations between quantum error correction (QEC) and tensor network (TN) methods of quantum manybody physics. We exhibit correspondences between wellknown families of QEC codes and TNs, and demonstrate a formal equivalence between decoding a QEC code and contracting a TN. We build on this equivalence to propose a new family of quantum codes and decoding algorithms that generalize and improve upon quantum polar codes and successive cancellation decoding in a natural way. 
DuclosCianci, Guillaume; Poulin, David FaultTolerant Renormalization Group Decoder for Abelian Topological Codes Article de journal Quant. Info. and Comp., 14 , p. 0721, 2014. @article{DP13b, title = {FaultTolerant Renormalization Group Decoder for Abelian Topological Codes}, author = {Guillaume DuclosCianci and David Poulin}, year = {2014}, date = {20140101}, journal = {Quant. Info. and Comp.}, volume = {14}, pages = {0721}, abstract = {We present a threedimensional generalization of a renormalization group decoding algorithm for topological codes with Abelian anyonic excitations that we previously introduced for two dimensions. This 3D implementation extends our previous 2D algorithm by incorporating a failure probability of the syndrome measurements, i.e., it enables faulttolerant decoding. We report a faulttolerant storage threshold of 1.9(4)% for Kitaev's toric code subject to a 3D bitflip channel (i.e. including imperfect syndrome measurements). This number is to be compared with the 2.9% value obtained via perfect matching. The 3D generalization inherits many properties of the 2D algorithm, including a complexity linear in the spacetime volume of the memory, which can be parallelized to logarithmic time.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We present a threedimensional generalization of a renormalization group decoding algorithm for topological codes with Abelian anyonic excitations that we previously introduced for two dimensions. This 3D implementation extends our previous 2D algorithm by incorporating a failure probability of the syndrome measurements, i.e., it enables faulttolerant decoding. We report a faulttolerant storage threshold of 1.9(4)% for Kitaev's toric code subject to a 3D bitflip channel (i.e. including imperfect syndrome measurements). This number is to be compared with the 2.9% value obtained via perfect matching. The 3D generalization inherits many properties of the 2D algorithm, including a complexity linear in the spacetime volume of the memory, which can be parallelized to logarithmic time. 
2013 
Brell, C G; Burton, S D; Dauphinais, G; Flammia, S T; Poulin, D Thermalization, ErrorCorrection, and Memory Lifetime for Ising Anyon Systems Divers 2013. @misc{BBDFP13, title = {Thermalization, ErrorCorrection, and Memory Lifetime for Ising Anyon Systems}, author = {C.G. Brell and S.D. Burton and G. Dauphinais and S.T. Flammia and D. Poulin}, year = {2013}, date = {20130101}, abstract = {We consider twodimensional lattice models that support Ising anyonic excitations and are coupled to a thermal bath. We propose a phenomenological model for the resulting shorttime dynamics that includes paircreation, hopping, braiding, and fusion of anyons. By explicitly constructing topological quantum errorcorrecting codes for this class of system, we use our thermalization model to estimate the lifetime of the quantum information stored in the encoded spaces. To decode and correct errors in these codes, we adapt several existing topological decoders to the nonAbelian setting. We perform largescale numerical simulations of these twodimensional Ising anyon systems and find that the thresholds of these models range between 13% to 25%. To our knowledge, these are the first numerical threshold estimates for quantum codes without explicit additive structure.}, keywords = {}, pubstate = {published}, tppubtype = {misc} } We consider twodimensional lattice models that support Ising anyonic excitations and are coupled to a thermal bath. We propose a phenomenological model for the resulting shorttime dynamics that includes paircreation, hopping, braiding, and fusion of anyons. By explicitly constructing topological quantum errorcorrecting codes for this class of system, we use our thermalization model to estimate the lifetime of the quantum information stored in the encoded spaces. To decode and correct errors in these codes, we adapt several existing topological decoders to the nonAbelian setting. We perform largescale numerical simulations of these twodimensional Ising anyon systems and find that the thresholds of these models range between 13% to 25%. To our knowledge, these are the first numerical threshold estimates for quantum codes without explicit additive structure. 
Kribs, D; Poulin, D Operator quantum error correction Article de journal Chapter in book Quantum Error Correction, (6), p. 163, 2013. @article{KP13a, title = {Operator quantum error correction}, author = {D. Kribs and D. Poulin}, editor = {D.A. Lidar and T.A. Brun}, year = {2013}, date = {20130101}, journal = {Chapter in book Quantum Error Correction}, number = {6}, pages = {163}, publisher = {Cambridge University Press, Cambridge}, keywords = {}, pubstate = {published}, tppubtype = {article} } 
Poulin, D Iterative quantum coding systems Article de journal Chapter in book Quantum error correction, (11), p. 279, 2013. @article{P13a, title = {Iterative quantum coding systems}, author = {D. Poulin}, editor = {D.A. Lidar and T.A. Brun}, year = {2013}, date = {20130101}, journal = {Chapter in book Quantum error correction}, number = {11}, pages = {279}, publisher = {Cambridge University Press}, keywords = {}, pubstate = {published}, tppubtype = {article} } 
Pelchat, Emilie; Poulin, David Degenerate Viterbi decoding Article de journal IEEE Trans. Info. Theor., 59 , p. 3915, 2013. @article{PP12a, title = {Degenerate Viterbi decoding}, author = {Emilie Pelchat and David Poulin}, year = {2013}, date = {20130101}, journal = {IEEE Trans. Info. Theor.}, volume = {59}, pages = {3915}, keywords = {}, pubstate = {published}, tppubtype = {article} } 
Ferris, Andrew J; Poulin, David Algorithms for the Markov Entropy Decomposition Article de journal Phys. Rev. B, 87 , p. 205126, 2013. @article{FP13a, title = {Algorithms for the Markov Entropy Decomposition}, author = {Ferris, Andrew J. and Poulin, David}, year = {2013}, date = {20130101}, urldate = {20121207}, journal = {Phys. Rev. B}, volume = {87}, pages = {205126}, abstract = {The Markov entropy decomposition (MED) is a recentlyproposed, clusterbased simulation method for finite temperature quantum systems with arbitrary geometry. In this paper, we detail numerical algorithms for performing the required steps of the MED, principally solving a minimization problem with a preconditioned Newton's algorithm, as well as how to extract global susceptibilities and thermal responses. We demonstrate the power of the method with the spin1/2 XXZ model on the 2D square lattice, including the extraction of critical points and details of each phase. Although the method shares some qualitative similarities with exactdiagonalization, we show the MED is both more accurate and significantly more flexible.}, keywords = {}, pubstate = {published}, tppubtype = {article} } The Markov entropy decomposition (MED) is a recentlyproposed, clusterbased simulation method for finite temperature quantum systems with arbitrary geometry. In this paper, we detail numerical algorithms for performing the required steps of the MED, principally solving a minimization problem with a preconditioned Newton's algorithm, as well as how to extract global susceptibilities and thermal responses. We demonstrate the power of the method with the spin1/2 XXZ model on the 2D square lattice, including the extraction of critical points and details of each phase. Although the method shares some qualitative similarities with exactdiagonalization, we show the MED is both more accurate and significantly more flexible. 
Ferris, Andrew J; Poulin, David Branching MERA codes: a natural extension of polar codes Divers 2013. @misc{FP13c, title = {Branching MERA codes: a natural extension of polar codes}, author = {Ferris, Andrew J. and Poulin, David}, year = {2013}, date = {20130101}, abstract = {We introduce a new class of circuits for constructing efficiently decodable errorcorrection codes, based on a recently discovered contractible tensor network. We perform an indepth study of a particular example that can be thought of as an extension to Arikan's polar code. Notably, our numerical simulation show that this code polarizes the logical channels more strongly while retaining the loglinear decoding complexity using the successive cancellation decoder. These codes also display improved errorcorrecting capability with only a minor impact on decoding complexity. Efficient decoding is realized using powerful graphical calculus tools developed in the field of quantum manybody physics. In a companion paper, we generalize our construction to the quantum setting and describe more indepth the relation between classical and quantum error correction and the graphical calculus of tensor networks.}, keywords = {}, pubstate = {published}, tppubtype = {misc} } We introduce a new class of circuits for constructing efficiently decodable errorcorrection codes, based on a recently discovered contractible tensor network. We perform an indepth study of a particular example that can be thought of as an extension to Arikan's polar code. Notably, our numerical simulation show that this code polarizes the logical channels more strongly while retaining the loglinear decoding complexity using the successive cancellation decoder. These codes also display improved errorcorrecting capability with only a minor impact on decoding complexity. Efficient decoding is realized using powerful graphical calculus tools developed in the field of quantum manybody physics. In a companion paper, we generalize our construction to the quantum setting and describe more indepth the relation between classical and quantum error correction and the graphical calculus of tensor networks. 
DuclosCianci, Guillaume; Poulin, David Kitaev's Z_dCodes Threshold Estimates Article de journal Phys. Rev. A, 87 , p. 062338, 2013. @article{DP13a, title = {Kitaev's Z_dCodes Threshold Estimates}, author = {Guillaume DuclosCianci and David Poulin}, year = {2013}, date = {20130101}, journal = {Phys. Rev. A}, volume = {87}, pages = {062338}, abstract = {We study the quantum error correction threshold of Kitaev's toric code over the group Z_d subject to a generalized bitflip noise. This problem requires novel decoding techniques, and for this purpose we generalize the renormalization group method we previously introduced for Z_2 topological codes.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We study the quantum error correction threshold of Kitaev's toric code over the group Z_d subject to a generalized bitflip noise. This problem requires novel decoding techniques, and for this purpose we generalize the renormalization group method we previously introduced for Z_2 topological codes. 
LandonCardinal, Olivier ; Poulin, David Local topological order inhibits thermal stability in 2D Article de journal Phys. Rev. Lett., 110 , p. 090502, 2013. @article{LP13a, title = {Local topological order inhibits thermal stability in 2D}, author = {LandonCardinal, Olivier and Poulin, David}, year = {2013}, date = {20130101}, journal = {Phys. Rev. Lett.}, volume = {110}, pages = {090502}, abstract = {We study the robustness of quantum information stored in the degenerate ground space of a local, frustrationfree Hamiltonian with commuting terms on a 2D spin lattice. On one hand, a macroscopic energy barrier separating the distinct ground states under local transformations would protect the information from thermal fluctuations. On the other hand, local topological order would shield the ground space from static perturbations. Here we demonstrate that local topological order implies a constant energy barrier, thus inhibiting thermal stability.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We study the robustness of quantum information stored in the degenerate ground space of a local, frustrationfree Hamiltonian with commuting terms on a 2D spin lattice. On one hand, a macroscopic energy barrier separating the distinct ground states under local transformations would protect the information from thermal fluctuations. On the other hand, local topological order would shield the ground space from static perturbations. Here we demonstrate that local topological order implies a constant energy barrier, thus inhibiting thermal stability. 
2012 
Denhez, Gabrielle; Blais, Alexandre; Poulin, David Quantum error correction benchmarks for continuous weak parity measurements Article de journal Phys. Rev. A, 86 , p. 032318, 2012. @article{DBP12a, title = {Quantum error correction benchmarks for continuous weak parity measurements}, author = {Gabrielle Denhez and Alexandre Blais and David Poulin}, year = {2012}, date = {20120101}, journal = {Phys. Rev. A}, volume = {86}, pages = {032318}, keywords = {}, pubstate = {published}, tppubtype = {article} } 
Brown, Winton ; Poulin, David Quantum Markov Networks and Commuting Hamiltonians Divers 2012. @misc{BP12a, title = {Quantum Markov Networks and Commuting Hamiltonians}, author = {Brown, Winton and Poulin, David}, year = {2012}, date = {20120101}, abstract = {Quantum Markov networks are a generalization of quantum Markov chains to arbitrary graphs. They provide a powerful classification of correlations in quantum manybody systemscomplementing the area law at finite temperatureand are therefore useful to understand the powers and limitations of certain classes of simulation algorithms. Here, we extend the characterization of quantum Markov networks and in particular prove the equivalence of positive quantum Markov networks and Gibbs states of Hamiltonians that are the sum of local commuting terms on graphs containing no triangles. For more general graphs we demonstrate the equivalence between quantum Markov networks and Gibbs states of a class of Hamiltonians of intermediate complexity between commuting and general local Hamiltonians.}, keywords = {}, pubstate = {published}, tppubtype = {misc} } Quantum Markov networks are a generalization of quantum Markov chains to arbitrary graphs. They provide a powerful classification of correlations in quantum manybody systemscomplementing the area law at finite temperatureand are therefore useful to understand the powers and limitations of certain classes of simulation algorithms. Here, we extend the characterization of quantum Markov networks and in particular prove the equivalence of positive quantum Markov networks and Gibbs states of Hamiltonians that are the sum of local commuting terms on graphs containing no triangles. For more general graphs we demonstrate the equivalence between quantum Markov networks and Gibbs states of a class of Hamiltonians of intermediate complexity between commuting and general local Hamiltonians. 
Denhez, Gabrielle; Blais, Alexandre; Poulin, David Quantum error correction benchmarks for continuous weak parity measurements Article de journal Phys. Rev. A, 86 , p. 032318, 2012. @article{DBP12ab, title = {Quantum error correction benchmarks for continuous weak parity measurements}, author = {Gabrielle Denhez and Alexandre Blais and David Poulin}, year = {2012}, date = {20120101}, journal = {Phys. Rev. A}, volume = {86}, pages = {032318}, keywords = {}, pubstate = {published}, tppubtype = {article} } 
Bombin, Hector; DuclosCianci, Guillaume; Poulin, David Universal topological phase of 2D stabilizer codes Article de journal New J. Phys., 14 , p. 073048, 2012. @article{BDP11a, title = {Universal topological phase of 2D stabilizer codes}, author = {Hector Bombin and Guillaume DuclosCianci and David Poulin}, year = {2012}, date = {20120101}, journal = {New J. Phys.}, volume = {14}, pages = {073048}, abstract = {Topological phases can be defined in terms of local equivalence: two systems are in the same topological phase if it is possible to transform one into the other by a local reorganization of its degrees of freedom. The classification of topological phases therefore amounts to the classification of longrange entanglement. Such local transformation could result, for instance, from the adiabatic continuation of one system’s Hamiltonian to the other. Here, we use this definition to study the topological phase of translationally invariant stabilizer codes in two spatial dimensions, and show that they all belong to one universal phase. We do this by constructing an explicit mapping from any such code to a number of copies of Kitaev’s code. Some of our results extend to some twodimensional (2D) subsystem codes, including topological subsystem codes. Error correction benefits from the corresponding local mappings. In particular, it enables us to use decoding algorithm developed for Kitaev’s code to decode any 2D stabilizer code and subsystem code.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Topological phases can be defined in terms of local equivalence: two systems are in the same topological phase if it is possible to transform one into the other by a local reorganization of its degrees of freedom. The classification of topological phases therefore amounts to the classification of longrange entanglement. Such local transformation could result, for instance, from the adiabatic continuation of one system’s Hamiltonian to the other. Here, we use this definition to study the topological phase of translationally invariant stabilizer codes in two spatial dimensions, and show that they all belong to one universal phase. We do this by constructing an explicit mapping from any such code to a number of copies of Kitaev’s code. Some of our results extend to some twodimensional (2D) subsystem codes, including topological subsystem codes. Error correction benefits from the corresponding local mappings. In particular, it enables us to use decoding algorithm developed for Kitaev’s code to decode any 2D stabilizer code and subsystem code. 
LandonCardinal, Olivier; Poulin, David Practical learning method for multiscale entangled states Article de journal New J. Phys., 14 , p. 085004, 2012. @article{LP12a, title = {Practical learning method for multiscale entangled states}, author = {Olivier LandonCardinal and David Poulin}, year = {2012}, date = {20120101}, journal = {New J. Phys.}, volume = {14}, pages = {085004}, abstract = {We describe a method for reconstructing multiscale entangled states from a small number of efficientlyimplementable measurements and fast postprocessing. The method only requires singleparticle measurements and the total number of measurements is polynomial in the number of particles. Data postprocessing for state reconstruction uses standard tools, namely matrix diagonalisation and conjugate gradient method, and scales polynomially with the number of particles. Our method prevents the buildup of errors from both numerical and experimental imperfections.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We describe a method for reconstructing multiscale entangled states from a small number of efficientlyimplementable measurements and fast postprocessing. The method only requires singleparticle measurements and the total number of measurements is polynomial in the number of particles. Data postprocessing for state reconstruction uses standard tools, namely matrix diagonalisation and conjugate gradient method, and scales polynomially with the number of particles. Our method prevents the buildup of errors from both numerical and experimental imperfections. 
2011 
Temme, K; Osborne, T J; Vollbrecht, K; Poulin, David; Verstraete, F Quantum Metropolis Sampling Article de journal Nature, 471 , p. 87, 2011. @article{TOVP11a, title = {Quantum Metropolis Sampling}, author = {K. Temme and T.J. Osborne and K. Vollbrecht and David Poulin and F. Verstraete}, year = {2011}, date = {20110301}, journal = {Nature}, volume = {471}, pages = {87}, abstract = {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 manybody quantum physics in condensedmatter, chemical and highenergy 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 smallscale implementation of this algorithm should be achievable with today’s technology.}, keywords = {}, pubstate = {published}, tppubtype = {article} } 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 manybody quantum physics in condensedmatter, chemical and highenergy 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 smallscale implementation of this algorithm should be achievable with today’s technology. 
Poulin, David; Quarry, Angie; Somma, Rolando D; Verstraete, Frank Quantum simulation of timedependent Hamiltonians and the convenient illusion of Hilbert space Article de journal Phys. Rev. Lett., 106 , p. 170501, 2011. @article{PQSV11a, title = {Quantum simulation of timedependent Hamiltonians and the convenient illusion of Hilbert space}, author = {David Poulin and Angie Quarry and Rolando D. Somma and Frank Verstraete}, year = {2011}, date = {20110101}, journal = {Phys. Rev. Lett.}, volume = {106}, pages = {170501}, abstract = {We consider the manifold of all quantum manybody states that can be generated by arbitrary timedependent local Hamiltonians in a time that scales polynomially in the system size, and showthat it occupies an exponentially small volume in Hilbert space. This implies that the overwhelming majority of states in Hilbert space are not physical as they can only be produced after an exponentially long time. We establish this fact by making use of a timedependent generalization of the SuzukiTrotter expansion, followed by a wellknown counting argument. This also demonstrates that a computational model based on arbitrarily}, keywords = {}, pubstate = {published}, tppubtype = {article} } We consider the manifold of all quantum manybody states that can be generated by arbitrary timedependent local Hamiltonians in a time that scales polynomially in the system size, and showthat it occupies an exponentially small volume in Hilbert space. This implies that the overwhelming majority of states in Hilbert space are not physical as they can only be produced after an exponentially long time. We establish this fact by making use of a timedependent generalization of the SuzukiTrotter expansion, followed by a wellknown counting argument. This also demonstrates that a computational model based on arbitrarily 
Poulin, David; Hastings, Matthew B Markov entropy decomposition: a variational dual for quantum belief propagation Article de journal Phys. Rev. Lett, 106 , p. 080403, 2011. @article{PH11a, title = {Markov entropy decomposition: a variational dual for quantum belief propagation}, author = {David Poulin and Matthew B. Hastings}, year = {2011}, date = {20110101}, journal = {Phys. Rev. Lett}, volume = {106}, pages = {080403}, abstract = {We present a lower bound for the free energy of a quantum manybody system at finite temperature. This lower bound is expressed as a convex optimization problem with linear constraints, and is derived using strong subadditivity of von Neumann entropy and a relaxation of the consistency condition of local density operators. The dual to this minimization problem leads to a set of quantum belief propagation equations, thus providing a firm theoretical foundation to that approach. The minimization problem is numerically tractable, and we find good agreement with quantum Monte Carlo for the spin1/2 Heisenberg antiferromagnet in two dimensions. This lower bound complements other variational upper bounds. We discuss applications to Hamiltonian complexity theory and give a generalization of the structure theorem to trees in an appendix.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We present a lower bound for the free energy of a quantum manybody system at finite temperature. This lower bound is expressed as a convex optimization problem with linear constraints, and is derived using strong subadditivity of von Neumann entropy and a relaxation of the consistency condition of local density operators. The dual to this minimization problem leads to a set of quantum belief propagation equations, thus providing a firm theoretical foundation to that approach. The minimization problem is numerically tractable, and we find good agreement with quantum Monte Carlo for the spin1/2 Heisenberg antiferromagnet in two dimensions. This lower bound complements other variational upper bounds. We discuss applications to Hamiltonian complexity theory and give a generalization of the structure theorem to trees in an appendix. 
da Silva, Marcus P; LandonCardinal, Olivier; Poulin, David Practical characterization of quantum devices without tomography Article de journal Phys. Rev. Lett., 107 , p. 210404, 2011. @article{SLP11a, title = {Practical characterization of quantum devices without tomography}, author = {Marcus P. {da Silva} and Olivier LandonCardinal and David Poulin}, year = {2011}, date = {20110101}, journal = {Phys. Rev. Lett.}, volume = {107}, pages = {210404}, abstract = {Quantum tomography is the main method used to assess the quality of quantum information processing devices. However, the amount of resources needed for quantum tomography is exponential in the device size. Part of the problem is that tomography generates much more information than is usually sought. Taking a more targeted approach, we develop schemes that enable (i) estimating the fidelity of an experiment to a theoretical ideal description, (ii) learning which description within a reduced subset best matches the experimental data. Both these approaches yield a significant reduction in resources compared to tomography. In particular, we demonstrate that fidelity can be estimated from a number of simple experiments that is independent of the system size, removing an important roadblock for the experimental study of larger quantum information processing units.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Quantum tomography is the main method used to assess the quality of quantum information processing devices. However, the amount of resources needed for quantum tomography is exponential in the device size. Part of the problem is that tomography generates much more information than is usually sought. Taking a more targeted approach, we develop schemes that enable (i) estimating the fidelity of an experiment to a theoretical ideal description, (ii) learning which description within a reduced subset best matches the experimental data. Both these approaches yield a significant reduction in resources compared to tomography. In particular, we demonstrate that fidelity can be estimated from a number of simple experiments that is independent of the system size, removing an important roadblock for the experimental study of larger quantum information processing units. 
2010 
Poulin, David LiebRobinson bound and locality for general Markovian quantum dynamics Article de journal Phys. Rev. Lett., 104 , p. 190401, 2010. @article{P10a, title = {LiebRobinson bound and locality for general Markovian quantum dynamics}, author = {David Poulin}, year = {2010}, date = {20100101}, journal = {Phys. Rev. Lett.}, volume = {104}, pages = {190401}, abstract = {The LiebRobinson 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 lengthscale set by the LiebRobinson velocity and the system's relaxation time.}, keywords = {}, pubstate = {published}, tppubtype = {article} } The LiebRobinson 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 lengthscale set by the LiebRobinson velocity and the system's relaxation time. 
Bilgin, E; Poulin, David Coarse grained belief propagation for simulation of interacting quantum systems at all temperatures Article de journal Phys. Rev. B, 81 , p. 054106, 2010. @article{BP10b, title = {Coarse grained belief propagation for simulation of interacting quantum systems at all temperatures}, author = {E. Bilgin and David Poulin}, year = {2010}, date = {20100101}, journal = {Phys. Rev. B}, volume = {81}, pages = {054106}, abstract = {We continue our numerical study of quantum belief propagation initiated in citePB08a. 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 onedimensional 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 citeLSS07a 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.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We continue our numerical study of quantum belief propagation initiated in citePB08a. 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 onedimensional 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 citeLSS07a 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. 
DuclosCianci, Guillaume; Poulin, David Fast decoders for topological quantum codes Article de journal Phys. Rev. Lett., 104 , p. 050504, 2010. @article{DP10a, title = {Fast decoders for topological quantum codes}, author = {Guillaume DuclosCianci and David Poulin}, year = {2010}, date = {20100101}, journal = {Phys. Rev. Lett.}, volume = {104}, pages = {050504}, abstract = {We present a family of algorithms, combining realspace 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 errorcorrecting codes. For a system of linear size $ell$, our algorithm runs in time $logell$ compared to $ell^6$ needed for the minimumweight perfect matching algorithm previously used in this context and achieves a higher depolarizing error threshold.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We present a family of algorithms, combining realspace 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 errorcorrecting codes. For a system of linear size $ell$, our algorithm runs in time $logell$ compared to $ell^6$ needed for the minimumweight perfect matching algorithm previously used in this context and achieves a higher depolarizing error threshold. 
DuclosCianci, Guillaume; Poulin, David A renormalization group decoding algorithm for topological quantum codes Inproceedings IEEE Information Theory Workshop, 2010. @inproceedings{DP10a1, title = {A renormalization group decoding algorithm for topological quantum codes}, author = {Guillaume DuclosCianci and David Poulin}, year = {2010}, date = {20100101}, booktitle = {IEEE Information Theory Workshop}, abstract = {Topological quantum errorcorrecting codes are defined by geometrically local checks on a twodimensional lattice of quantum bits (qubits), making them particularly well suited for faulttolerant quantum information processing. Here, we present a decoding algorithm for topological codes that is faster than previously known algorithms and applies to a wider class of topological codes. Our algorithm makes use of two methods inspired from statistical physics: renormalization groups and meanfield approximations. First, the topological code is approximated by a concatenated block code that can be efficiently decoded. To improve this approximation, additional consistency conditions are imposed between the blocks, and are solved by a belief propagation algorithm.}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } Topological quantum errorcorrecting codes are defined by geometrically local checks on a twodimensional lattice of quantum bits (qubits), making them particularly well suited for faulttolerant quantum information processing. Here, we present a decoding algorithm for topological codes that is faster than previously known algorithms and applies to a wider class of topological codes. Our algorithm makes use of two methods inspired from statistical physics: renormalization groups and meanfield approximations. First, the topological code is approximated by a concatenated block code that can be efficiently decoded. To improve this approximation, additional consistency conditions are imposed between the blocks, and are solved by a belief propagation algorithm. 
Cramer, M; Plenio, M B; Flammia, S T; Somma, R; Gross, D; Bartlett, S D; LandonCardinal, O; Poulin, D; Liu, Y K Efficient quantum state tomography Article de journal Nature Comm., 1 , p. 149, 2010. @article{CPFS10a, title = {Efficient quantum state tomography}, author = {M. Cramer and M.B. Plenio and S.T. Flammia and R. Somma and D. Gross and S.D. Bartlett and O. LandonCardinal and D. Poulin and Y.K. Liu}, year = {2010}, date = {20100101}, journal = {Nature Comm.}, volume = {1}, pages = {149}, abstract = {Quantum 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 postprocessing. Both rely only on a linear number of experimental operations and postprocessing 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.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Quantum 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 postprocessing. Both rely only on a linear number of experimental operations and postprocessing 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. 
BlumeKohout, R; Ng, H K; Poulin, D; Viola, L Information preserving structures: a general framework for quantum zeroerror information Article de journal Phys. Rev. A, 82 , p. 062306, 2010. @article{BNPV10a, title = {Information preserving structures: a general framework for quantum zeroerror information}, author = {R. BlumeKohout and H.K. Ng and D. Poulin and L. Viola}, year = {2010}, date = {20100101}, journal = {Phys. Rev. A}, volume = {82}, pages = {062306}, abstract = {Quantum 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 measurementstabilized and unconditionally preserved codes. Finally, for several of these operational critera, we present efficient [polynomial in the statespace dimension] algorithms to find all of a channel's informationpreserving structures.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Quantum 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 measurementstabilized and unconditionally preserved codes. Finally, for several of these operational critera, we present efficient [polynomial in the statespace dimension] algorithms to find all of a channel's informationpreserving structures. 
Bravyi, S; Poulin, D; Terhal, B M Tradeoffs for reliable quantum information storage in 2D systems Inproceedings Horodecki, R; Kilin, Ya. S; Kowalik, J (Ed.): Quantum Cryptography and Computing, p. 125, 2010. @inproceedings{BPT10b, title = {Tradeoffs for reliable quantum information storage in 2D systems}, author = {S. Bravyi and D. Poulin and B.M. Terhal}, editor = {R. Horodecki and S. Ya. Kilin and J. Kowalik}, year = {2010}, date = {20100101}, booktitle = {Quantum Cryptography and Computing}, pages = {125}, keywords = {}, pubstate = {published}, tppubtype = {inproceedings} } 
Bravyi, S; Poulin, David; Terhal, B M Tradeoffs for reliable quantum information storage in 2D systems Article de journal Phys. Rev. Lett., 104 , p. 050503, 2010. @article{BPT10a, title = {Tradeoffs for reliable quantum information storage in 2D systems}, author = {S. Bravyi and David Poulin and B.M. Terhal}, year = {2010}, date = {20100101}, journal = {Phys. Rev. Lett.}, volume = {104}, pages = {050503}, abstract = {We 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 finitedimensional 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 $ksqrtđ =O(n)$.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We 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 finitedimensional 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 $ksqrtđ =O(n)$. 
2009 
Poulin, D; Tillich, J P; Ollivier, H Quantum serial turbocodes Article de journal IEEE Trans. Info. Theor., 55 (6), p. 2776, 2009. @article{PTO09a, title = {Quantum serial turbocodes}, author = {D. Poulin and J.P. Tillich and H. Ollivier}, year = {2009}, date = {20090101}, journal = {IEEE Trans. Info. Theor.}, volume = {55}, number = {6}, pages = {2776}, abstract = {We present a theory of quantum serial turbocodes, 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 4cycles 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 noncatastrophic and nonrecursive. While the resulting families of turbocodes 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.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We present a theory of quantum serial turbocodes, 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 4cycles 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 noncatastrophic and nonrecursive. While the resulting families of turbocodes 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. 
Poulin, David; Wocjan, Pawel Sampling from the quantum Gibbs state and evaluating partition functions with a quantum computer Article de journal Phys. Rev. Lett., 103 , p. 220502, 2009. @article{PW09b, title = {Sampling from the quantum Gibbs state and evaluating partition functions with a quantum computer}, author = {David Poulin and Pawel Wocjan}, year = {2009}, date = {20090101}, journal = {Phys. Rev. Lett.}, volume = {103}, pages = {220502}, abstract = {We 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.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We 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. 
Poulin, David; Wocjan, Pawel Preparing ground states of quantum manybody systems on a quantum computer Article de journal Phys. Rev. Lett., 102 , p. 130503, 2009. @article{PW09a, title = {Preparing ground states of quantum manybody systems on a quantum computer}, author = {David Poulin and Pawel Wocjan}, year = {2009}, date = {20090101}, journal = {Phys. Rev. Lett.}, volume = {102}, pages = {130503}, abstract = {Preparing the ground state of a system of interacting classical particles is an NPhard 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.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Preparing the ground state of a system of interacting classical particles is an NPhard 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. 
2008 
Poulin, D; Bilgin, E Belief propagation algorithm for computing correlation functions in finitetemperature quantum manybody systems on loopy graphs Article de journal Phys. Rev. A, 77 , p. 052318, 2008. @article{PB08a, title = {Belief propagation algorithm for computing correlation functions in finitetemperature quantum manybody systems on loopy graphs}, author = {D. Poulin and E. Bilgin}, year = {2008}, date = {20080101}, journal = {Phys. Rev. A}, volume = {77}, pages = {052318}, abstract = {Belief 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 finitetemperature quantum manybody physics. Our results indicate that QBP provides reliable estimates of the hightemperature 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.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Belief 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 finitetemperature quantum manybody physics. Our results indicate that QBP provides reliable estimates of the hightemperature 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. 
Poulin, D; Chung, Y On the iterative decoding of sparse quantum codes Article de journal Quant. Info. and Comp., 8 , p. 986, 2008. @article{PC08a, title = {On the iterative decoding of sparse quantum codes}, author = {D. Poulin and Y. Chung}, year = {2008}, date = {20080101}, journal = {Quant. Info. and Comp.}, volume = {8}, pages = {986}, abstract = {We 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.}, keywords = {}, pubstate = {published}, tppubtype = {article} } We 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. 
Poulin, David; Tillich, JeanPierre; Ollivier, Harold Quantum serial turbocodes 5500  5599 Conférence ISIT'08, IEEE, 2008. @conference{PTO08a, title = {Quantum serial turbocodes}, author = {David Poulin and JeanPierre Tillich and Harold Ollivier}, year = {2008}, date = {20080101}, booktitle = {ISIT'08}, publisher = {IEEE}, abstract = {We present a theory of quantum serial turbocodes and study their performance numerically on a depolarization channel. These codes can be considered as a generalization of classical serial turbocodes. 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 4cycles 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 turbocodes, namely the character of being recursive and noncatastrophic. 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 noncatastrophic and nonrecursive. While the resulting families of turbocodes 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.}, keywords = {}, pubstate = {published}, tppubtype = {conference} } We present a theory of quantum serial turbocodes and study their performance numerically on a depolarization channel. These codes can be considered as a generalization of classical serial turbocodes. 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 4cycles 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 turbocodes, namely the character of being recursive and noncatastrophic. 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 noncatastrophic and nonrecursive. While the resulting families of turbocodes 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. 
Girelli, F; Poulin, D Quantum reference frames and deformed symmetries Article de journal Phys. Rev. D, 77 , p. 104012, 2008. @article{GP08a, title = {Quantum reference frames and deformed symmetries}, author = {F. Girelli and D. Poulin}, year = {2008}, date = {20080101}, journal = {Phys. Rev. D}, volume = {77}, pages = {104012}, abstract = {In 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 "backaction" that modifies its properties. In a quantumgravitational setting, it has been argued that such a backaction 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.}, keywords = {}, pubstate = {published}, tppubtype = {article} } In 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 "backaction" that modifies its properties. In a quantumgravitational setting, it has been argued that such a backaction 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. 
Leifer, M S; Poulin, D Quantum graphical models and belief propagation Article de journal Ann. Phys., 323 , p. 1899, 2008. @article{LP08a, title = {Quantum graphical models and belief propagation}, author = {M.S. Leifer and D. Poulin}, year = {2008}, date = {20080101}, journal = {Ann. Phys.}, volume = {323}, pages = {1899}, abstract = {Belief 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, operatorvalued, generalization of classical probability theory. Some novel characterizations of quantum conditional independence are derived, and definitions of Quantum nBifactor 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 HammerselyClifford theorem. A Quantum Belief Propagation algorithm is presented and is shown to converge on 1Bifactor 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 manybody quantum systems are described.}, keywords = {}, pubstate = {published}, tppubtype = {article} } Belief 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, operatorvalued, generalization of classical probability theory. Some novel characterizations of quantum conditional independence are derived, and definitions of Quantum nBifactor 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 HammerselyClifford theorem. A Quantum Belief Propagation algorithm is presented and is shown to converge on 1Bifactor 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 manybody quantum systems are described. 
Équipe
Notice: Uninitialized string offset: 0 in /home/ab52337/public_html/marcl/quantique/wpcontent/themes/bravad/content/profil/profilequipe.php on line 124
Notice: Uninitialized string offset: 0 in /home/ab52337/public_html/marcl/quantique/wpcontent/themes/bravad/content/profil/profilequipe.php on line 124
Notice: Uninitialized string offset: 0 in /home/ab52337/public_html/marcl/quantique/wpcontent/themes/bravad/content/profil/profilequipe.php on line 124
Notice: Uninitialized string offset: 0 in /home/ab52337/public_html/marcl/quantique/wpcontent/themes/bravad/content/profil/profilequipe.php on line 124
Notice: Uninitialized string offset: 0 in /home/ab52337/public_html/marcl/quantique/wpcontent/themes/bravad/content/profil/profilequipe.php on line 124
Notice: Uninitialized string offset: 0 in /home/ab52337/public_html/marcl/quantique/wpcontent/themes/bravad/content/profil/profilequipe.php on line 124
Notice: Uninitialized string offset: 0 in /home/ab52337/public_html/marcl/quantique/wpcontent/themes/bravad/content/profil/profilequipe.php on line 124
Notice: Uninitialized string offset: 0 in /home/ab52337/public_html/marcl/quantique/wpcontent/themes/bravad/content/profil/profilequipe.php on line 124