Quantum mixing of Markov chains for special distributions
The preparation of the stationary distribution of irreducible, time-reversible Markov chains (MCs) is a fundamental building block in many heuristic approaches to algorithmically hard problems. It has been conjectured that quantum analogs of classical mixing processes may offer a generic quadratic s...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IOP Publishing
2015-01-01
|
| Series: | New Journal of Physics |
| Subjects: | |
| Online Access: | https://doi.org/10.1088/1367-2630/17/7/073004 |
| _version_ | 1797751185401184256 |
|---|---|
| author | V Dunjko H J Briegel |
| author_facet | V Dunjko H J Briegel |
| author_sort | V Dunjko |
| collection | DOAJ |
| description | The preparation of the stationary distribution of irreducible, time-reversible Markov chains (MCs) is a fundamental building block in many heuristic approaches to algorithmically hard problems. It has been conjectured that quantum analogs of classical mixing processes may offer a generic quadratic speed-up in realizing such stationary distributions. Such a speed-up would also imply a speed-up of a broad family of heuristic algorithms. However, a true quadratic speed up has thus far only been demonstrated for special classes of MCs. These results often presuppose a regular structure of the underlying graph of the MC, and also a regularity in the transition probabilities. In this work, we demonstrate a true quadratic speed-up for a class of MCs where the restriction is only on the form of the stationary distribution, rather than directly on the MC structure itself. In particular, we show efficient mixing can be achieved when it is known beforehand that the distribution is monotonically decreasing relative to a known order on the state space. Following this, we show that our approach extends to a wider class of distributions, where only a fraction of the shape of the distribution is known to be monotonic. Our approach is built on the Szegedy-type quantization of transition operators. |
| first_indexed | 2024-03-12T16:43:50Z |
| format | Article |
| id | doaj.art-b9377dec42d04d9db32b0585b3523e23 |
| institution | Directory Open Access Journal |
| issn | 1367-2630 |
| language | English |
| last_indexed | 2024-03-12T16:43:50Z |
| publishDate | 2015-01-01 |
| publisher | IOP Publishing |
| record_format | Article |
| series | New Journal of Physics |
| spelling | doaj.art-b9377dec42d04d9db32b0585b3523e232023-08-08T14:19:49ZengIOP PublishingNew Journal of Physics1367-26302015-01-0117707300410.1088/1367-2630/17/7/073004Quantum mixing of Markov chains for special distributionsV Dunjko0H J Briegel1Institute for Theoretical Physics, University of Innsbruck , Technikerstraße 25, A-6020 Innsbruck, Austria; Laboratory of Evolutionary Genetics, Division of Molecular Biology, Ruđer Bošković Institute, Bijenička cesta 54, HR-10000 Zagreb, CroatiaInstitute for Theoretical Physics, University of Innsbruck , Technikerstraße 25, A-6020 Innsbruck, AustriaThe preparation of the stationary distribution of irreducible, time-reversible Markov chains (MCs) is a fundamental building block in many heuristic approaches to algorithmically hard problems. It has been conjectured that quantum analogs of classical mixing processes may offer a generic quadratic speed-up in realizing such stationary distributions. Such a speed-up would also imply a speed-up of a broad family of heuristic algorithms. However, a true quadratic speed up has thus far only been demonstrated for special classes of MCs. These results often presuppose a regular structure of the underlying graph of the MC, and also a regularity in the transition probabilities. In this work, we demonstrate a true quadratic speed-up for a class of MCs where the restriction is only on the form of the stationary distribution, rather than directly on the MC structure itself. In particular, we show efficient mixing can be achieved when it is known beforehand that the distribution is monotonically decreasing relative to a known order on the state space. Following this, we show that our approach extends to a wider class of distributions, where only a fraction of the shape of the distribution is known to be monotonic. Our approach is built on the Szegedy-type quantization of transition operators.https://doi.org/10.1088/1367-2630/17/7/073004quantum walksquantum mixingMarkov chain Monte Carlo |
| spellingShingle | V Dunjko H J Briegel Quantum mixing of Markov chains for special distributions New Journal of Physics quantum walks quantum mixing Markov chain Monte Carlo |
| title | Quantum mixing of Markov chains for special distributions |
| title_full | Quantum mixing of Markov chains for special distributions |
| title_fullStr | Quantum mixing of Markov chains for special distributions |
| title_full_unstemmed | Quantum mixing of Markov chains for special distributions |
| title_short | Quantum mixing of Markov chains for special distributions |
| title_sort | quantum mixing of markov chains for special distributions |
| topic | quantum walks quantum mixing Markov chain Monte Carlo |
| url | https://doi.org/10.1088/1367-2630/17/7/073004 |
| work_keys_str_mv | AT vdunjko quantummixingofmarkovchainsforspecialdistributions AT hjbriegel quantummixingofmarkovchainsforspecialdistributions |