{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,3]],"date-time":"2026-02-03T18:40:58Z","timestamp":1770144058310,"version":"3.49.0"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T00:00:00Z","timestamp":1719532800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T00:00:00Z","timestamp":1719532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["LAMARR"],"award-info":[{"award-number":["LAMARR"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003185","name":"Fraunhofer-Gesellschaft","doi-asserted-by":"publisher","award":["Quantum Now!"],"award-info":[{"award-number":["Quantum Now!"]}],"id":[{"id":"10.13039\/501100003185","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Graphical models are useful tools for describing structured high-dimensional probability distributions. The development of efficient algorithms for generating samples thereof remains an active research topic. In this work, we provide a quantum algorithm that enables the generation of unbiased and independent samples from general discrete graphical models. To this end, we identify a coherent embedding of the graphical model based on a repeat-until-success sampling scheme which clearly identifies whether a drawn sample represents the underlying distribution. Furthermore, we show that the success probability for finding a valid sample can be lower bounded with a quantity that depends on the number of maximal cliques and the model parameter norm. Moreover, we rigorously proof that the quantum embedding conserves the key property of graphical models, i.e., factorization over the cliques of the underlying conditional independence structure. The quantum sampling algorithm also allows for maximum likelihood learning as well as maximum a posteriori state approximation for the graphical model. Finally, the proposed quantum method shows potential to realize interesting problems on near-term quantum processors. In fact, illustrative experiments demonstrate that our method can carry out sampling and parameter learning not only with idealized simulations of quantum computers but also on actual quantum hardware solely supported by simple readout error mitigation.<\/jats:p>","DOI":"10.1007\/s42484-024-00175-y","type":"journal-article","created":{"date-parts":[[2024,6,28]],"date-time":"2024-06-28T10:03:34Z","timestamp":1719569014000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Quantum circuits for discrete graphical models"],"prefix":"10.1007","volume":"6","author":[{"given":"Nico","family":"Piatkowski","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christa","family":"Zoufal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,28]]},"reference":[{"key":"175_CR1","doi-asserted-by":"publisher","unstructured":"Abraham H et al (2019) Qiskit: an open-source framework for quantum computing. https:\/\/doi.org\/10.5281\/zenodo.2562110","DOI":"10.5281\/zenodo.2562110"},{"key":"175_CR2","doi-asserted-by":"crossref","unstructured":"Amin MH, Andriyash E, Rolfe J, Kulchytskyy B, Melko R (2018) Quantum Boltzmann machine. Phys Rev X 8","DOI":"10.1103\/PhysRevX.8.021050"},{"issue":"1\u20132","key":"175_CR3","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1020281327116","volume":"50","author":"C Andrieu","year":"2003","unstructured":"Andrieu C, Freitas N, Doucet A, Jordan MI (2003) An introduction to MCMC for machine learning. Mach Learn 50(1\u20132):5\u201343. https:\/\/doi.org\/10.1023\/A:1020281327116","journal-title":"Mach Learn"},{"issue":"3","key":"175_CR4","doi-asserted-by":"publisher","first-page":"179","DOI":"10.2307\/2987782","volume":"24","author":"J Besag","year":"1975","unstructured":"Besag J (1975) Statistical analysis of non-lattice data. J Royal Stat Soc Ser D (The Statistician). 24(3):179\u2013195. https:\/\/doi.org\/10.2307\/2987782","journal-title":"J Royal Stat Soc Ser D (The Statistician)."},{"key":"175_CR5","doi-asserted-by":"publisher","unstructured":"Bhattacharyya D (2021) Scalable noisy image restoration using quantum Markov random field. Thesis. https:\/\/doi.org\/10.13016\/m2ozmj-s7eg","DOI":"10.13016\/m2ozmj-s7eg"},{"key":"175_CR6","unstructured":"Brassard G, H\u00f8yer P, Mosca M, Montreal A, Aarhus BU, Waterloo CU (2000) Quantum amplitude amplification and estimation. arXiv: Quantum Physics"},{"key":"175_CR7","unstructured":"Bravyi S, Chowdhury A, Gosset D, Wocjan P (2021) On the complexity of quantum partition functions"},{"key":"175_CR8","doi-asserted-by":"publisher","unstructured":"Bubley R, Dyer ME (1997) Path coupling: a technique for provingrapid mixing in Markov chains. In: Foundations of Computer Science FOCS. pp 223\u2013231. https:\/\/doi.org\/10.1109\/SFCS.1997.646111","DOI":"10.1109\/SFCS.1997.646111"},{"key":"175_CR9","doi-asserted-by":"publisher","unstructured":"Dallaire-Demers P-L, Killoran N (2018) Quantum generative adversarial networks. Phys Rev A 98. https:\/\/doi.org\/10.1103\/PhysRevA.98.012324","DOI":"10.1103\/PhysRevA.98.012324"},{"issue":"6","key":"175_CR10","doi-asserted-by":"publisher","first-page":"721","DOI":"10.1109\/TPAMI.1984.4767596","volume":"6","author":"S Geman","year":"1984","unstructured":"Geman S, Geman D (1984) Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. IEEE Trans Pattern Anal Mach Intell 6(6):721\u2013741. https:\/\/doi.org\/10.1109\/TPAMI.1984.4767596","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"175_CR11","doi-asserted-by":"publisher","unstructured":"Gily\u00e9n A, Su Y, Low GH, Wiebe N (2019) Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. ACM SIGACT Symp Theor Comput. https:\/\/doi.org\/10.1145\/3313276.3316366","DOI":"10.1145\/3313276.3316366"},{"key":"175_CR12","doi-asserted-by":"publisher","unstructured":"Grover LK (2005) Fixed-point quantum search. Phys Rev Lett 95(15). https:\/\/doi.org\/10.1103\/physrevlett.95.150501","DOI":"10.1103\/physrevlett.95.150501"},{"key":"175_CR13","unstructured":"Hammersley JM, Clifford P (1971) Markov fields on finite graphs and lattices. Unpublished manuscript"},{"issue":"1","key":"175_CR14","doi-asserted-by":"publisher","first-page":"97","DOI":"10.2307\/2334940","volume":"57","author":"WK Hastings","year":"1970","unstructured":"Hastings WK (1970) Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1):97\u2013109. https:\/\/doi.org\/10.2307\/2334940","journal-title":"Biometrika"},{"key":"175_CR15","first-page":"1268","volume":"26","author":"T Hazan","year":"2013","unstructured":"Hazan T, Maji S, Jaakkola TS (2013) On sampling from the Gibbs distribution with random maximum a-posteriori perturbations. Adv Neural Inf Process Syst 26:1268\u20131276","journal-title":"Adv Neural Inf Process Syst"},{"issue":"7","key":"175_CR16","doi-asserted-by":"publisher","first-page":"1347","DOI":"10.1142\/s0129183199001108","volume":"10","author":"T Hogg","year":"1999","unstructured":"Hogg T, Mochon C, Polak W, Rieffel E (1999) Tools for quantum algorithms. Int J Mod Phys C 10(7):1347\u20131361. https:\/\/doi.org\/10.1142\/s0129183199001108","journal-title":"Int J Mod Phys C"},{"key":"175_CR17","unstructured":"IBM Quantum (2021). https:\/\/quantum-computing.ibm.com\/"},{"key":"175_CR18","unstructured":"Jerrum M, Sinclair A (1997) Approximation algorithms for NP-hard problems. PWS Publishing Co., Boston, MA, USA. Chap. The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration. pp 482\u2013520"},{"issue":"7","key":"175_CR19","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1089\/cmb.2007.0131","volume":"15","author":"H Kamisetty","year":"2008","unstructured":"Kamisetty H, Xing EP, Langmead CJ (2008) Free energy estimates of all-atom protein structures using generalized belief propagation. J Comput Biol 15(7):755\u2013766. https:\/\/doi.org\/10.1089\/cmb.2007.0131","journal-title":"J Comput Biol"},{"key":"175_CR20","doi-asserted-by":"crossref","unstructured":"Kieferov\u00e1 M, Wiebe N (2017) Tomography and generative training with quantum Boltzmann machines. Phys Rev A 96","DOI":"10.1103\/PhysRevA.96.062327"},{"key":"175_CR21","unstructured":"Kingma DP, Ba J (2015).: Adam: a method for stochastic optimization. In: International Conference on Learning Representations (ICLR)"},{"key":"175_CR22","unstructured":"Lafferty J, McCallum A, Pereira F (2001) Conditional random fields: probabilistic models for segmenting and labeling sequence data. International Conference on Machine Learning (ICML). pp 282\u2013289"},{"key":"175_CR23","doi-asserted-by":"publisher","first-page":"062315","DOI":"10.1103\/PhysRevA.89.062315","volume":"89","author":"GH Low","year":"2014","unstructured":"Low GH, Yoder TJ, Chuang IL (2014) Quantum inference on Bayesian networks. Phys Rev A 89:062315. https:\/\/doi.org\/10.1103\/PhysRevA.89.062315","journal-title":"Phys Rev A"},{"key":"175_CR24","doi-asserted-by":"publisher","unstructured":"McArdle S, Jones T, Endo S, Li Y, Benjamin SC, Yuan X (2019) Variational ansatz-based quantum simulation of imaginary time evolution. NPJ Quantum Inf 5(75). https:\/\/doi.org\/10.1038\/s41534-019-0187-2","DOI":"10.1038\/s41534-019-0187-2"},{"issue":"6","key":"175_CR25","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1063\/1.1699114","volume":"21","author":"N Metropolis","year":"1953","unstructured":"Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equations of state calculations by fast computing machine. J Chem Phys 21(6):1087\u20131091. https:\/\/doi.org\/10.1063\/1.1699114","journal-title":"J Chem Phys"},{"key":"175_CR26","doi-asserted-by":"publisher","first-page":"040326","DOI":"10.1103\/PRXQuantum.2.040326","volume":"2","author":"PD Nation","year":"2021","unstructured":"Nation PD, Kang H, Sundaresan N, Gambetta JM (2021) Scalable mitigation of measurement errors on quantum computers. PRX Quantum. 2:040326. https:\/\/doi.org\/10.1103\/PRXQuantum.2.040326","journal-title":"PRX Quantum."},{"key":"175_CR27","doi-asserted-by":"crossref","unstructured":"Nelson J, Vuffray M, Lokhov AY, Albash T, Coffrin C (2021) High-quality thermal Gibbs sampling with quantum annealing hardware","DOI":"10.1103\/PhysRevApplied.17.044046"},{"key":"175_CR28","volume-title":"Quantum computation and quantum information (10th Anniversary Edition)","author":"MA Nielsen","year":"2016","unstructured":"Nielsen MA, Chuang IL (2016) Quantum computation and quantum information (10th Anniversary Edition). Cambridge University Press"},{"key":"175_CR29","unstructured":"Niepert M, Minervini P, Franceschi L (2021) Implicit MLE: backpropagating through discrete exponential family distributions. In: Advances in neural information processing systems 34"},{"issue":"1","key":"175_CR30","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/BF02480944","volume":"33","author":"Y Ogata","year":"1981","unstructured":"Ogata Y, Tanemura M (1981) Estimation of interaction potentials of spatial point patterns through the maximum likelihood procedure. Ann Inst Stat Math 33(1):315\u2013338. https:\/\/doi.org\/10.1007\/BF02480944","journal-title":"Ann Inst Stat Math"},{"key":"175_CR31","doi-asserted-by":"crossref","unstructured":"Papandreou G, Yuille AL (2011) Perturb-and-MAP random fields: using discrete optimization to learn and sample from energy models. In: IEEE International Conference on Computer Vision (ICCV). pp 193\u2013200","DOI":"10.1109\/ICCV.2011.6126242"},{"key":"175_CR32","doi-asserted-by":"crossref","unstructured":"Peruzzo A, McClean J, Shadbolt P, Yung M-H, Zhou X-Q, Love PJ, Aspuru-Guzik A, O\u2019Brien JL (2014) A variational eigenvalue solver on a photonic quantum processor. Nat Commun 5(1):4213","DOI":"10.1038\/ncomms5213"},{"key":"175_CR33","unstructured":"Piatkowski N (2018) Exponential families on resource-constrained systems. PhD thesis, Technical University of Dortmund, Germany. http:\/\/hdl.handle.net\/2003\/36877"},{"issue":"1","key":"175_CR34","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10994-013-5399-7","volume":"93","author":"N Piatkowski","year":"2013","unstructured":"Piatkowski N, Lee S, Morik K (2013) Spatio-temporal random fields: compressible representation and distributed estimation. Mach Learn 93(1):115\u2013139. https:\/\/doi.org\/10.1007\/s10994-013-5399-7","journal-title":"Mach Learn"},{"key":"175_CR35","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1017\/S0305004100019307","volume":"32","author":"EJG Pitman","year":"1936","unstructured":"Pitman EJG (1936) Sufficient statistics and intrinsic accuracy. Math Proc Cambridge Philos Soc 32:567\u2013579","journal-title":"Math Proc Cambridge Philos Soc"},{"key":"175_CR36","doi-asserted-by":"publisher","unstructured":"Potamianos G, Goutsias J (1997) Stochastic approximation algorithms for partition function estimation of Gibbs random fields. IEEE Trans Inf Theory 43(6):1948\u20131965. https:\/\/doi.org\/10.1109\/18.641558","DOI":"10.1109\/18.641558"},{"key":"175_CR37","unstructured":"Somma R, Ortiz G, Gubernatis JE, Knill E, Laflamme R Simulating Physical Phenomena by Quantum Networks"},{"key":"175_CR38","doi-asserted-by":"crossref","unstructured":"Steutel FW, Harn van K (2004) Infinite divisibility of probability distributions on the real line. Pure and applied mathematics : a series of monographs and textbooks. Marcel Dekker Inc","DOI":"10.1201\/9780203014127"},{"key":"175_CR39","first-page":"1829","volume":"7","author":"MJ Wainwright","year":"2006","unstructured":"Wainwright MJ (2006) Estimating the \u201cwrong\" graphical model: benefits in the computation-limited setting. J Mach Learn Res 7:1829\u20131859","journal-title":"J Mach Learn Res"},{"issue":"1\u20132","key":"175_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000001","volume":"1","author":"MJ Wainwright","year":"2008","unstructured":"Wainwright MJ, Jordan MI (2008) Graphical models, exponential families, and variational inference. Found Trends Mach Learn 1(1\u20132):1\u2013305","journal-title":"Found Trends Mach Learn"},{"issue":"11","key":"175_CR41","doi-asserted-by":"publisher","first-page":"1610","DOI":"10.1016\/j.cviu.2013.07.004","volume":"117","author":"C Wang","year":"2013","unstructured":"Wang C, Komodakis N, Paragios N (2013) Markov random field modeling, inference & learning in computer vision & image understanding: a survey. Comput Vis Image Underst 117(11):1610\u20131627. https:\/\/doi.org\/10.1016\/j.cviu.2013.07.004","journal-title":"Comput Vis Image Underst"},{"key":"175_CR42","unstructured":"Wiebe N, Wossnig L (2019) Generative training of quantum Boltzmann machines with hidden units. arXiv:1905.09902"},{"key":"175_CR43","doi-asserted-by":"crossref","unstructured":"Yin Z, Collins R (2007) Belief propagation in a 3D spatio-temporal MRF for moving object detection. IEEE Comput Vision Patt Recognit","DOI":"10.1109\/CVPR.2007.383184"},{"key":"175_CR44","doi-asserted-by":"publisher","unstructured":"Yoder TJ, Low GH, Chuang IL (2014) Fixed-point quantum search with an optimal number of queries. Phys Rev Lett 113(21). https:\/\/doi.org\/10.1103\/physrevlett.113.210501","DOI":"10.1103\/physrevlett.113.210501"},{"key":"175_CR45","doi-asserted-by":"crossref","unstructured":"Yuan X, Endo S, Zhao Q, Li Y, Benjamin SC (2019) Theory of variational quantum simulation. Quantum. 3","DOI":"10.22331\/q-2019-10-07-191"},{"key":"175_CR46","unstructured":"Zhao L, Yang S, Rebentrost P (2021) Quantum algorithm for structure learning of Markov random fields"},{"key":"175_CR47","unstructured":"Zoufal C (2021) Generative quantum machine learning"},{"key":"175_CR48","doi-asserted-by":"publisher","unstructured":"Zoufal C, Lucchi A, Woerner S (2021) Variational quantum Boltzmann machines. Quantum Mach Intell 3(1). https:\/\/doi.org\/10.1007\/s42484-020-00033-7","DOI":"10.1007\/s42484-020-00033-7"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00175-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-024-00175-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-024-00175-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,23]],"date-time":"2024-12-23T16:20:14Z","timestamp":1734970814000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-024-00175-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,28]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["175"],"URL":"https:\/\/doi.org\/10.1007\/s42484-024-00175-y","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,6,28]]},"assertion":[{"value":"21 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 June 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interest"}}],"article-number":"37"}}