Application
Quantum Markov chain algorithms
GICC + MATHQI
Group description:
The Complutense University of Madrid (UCM) has two research groups specializing in quantum computing, QICC and MATHQI, and is interested in collaborating with other project partners for the development, expansion, and dissemination of this technology. In order to advance research in quantum computing within the fields of its scientific interest, UCM will undertake the activities described in the following section, within the framework of the Quantum Spain project.
The QICC and MATHQI groups, led respectively by professors Miguel Ángel Martín-Delgado and David Pérez-García, have extensive experience in the mathematical analysis of concepts related to quantum computing, as well as in the simulation of quantum systems with tensor networks. The research tasks of these UCM groups will focus on the study of tensor networks and the use of quantum Markov chains in processes related to artificial intelligence.
Activity description:
Quantum Markov chain algorithms are stochastic methods for reproducing probability distributions, which show convergence advantages over classical equivalents. These chains have proven their utility in optimizing a complex problem: protein folding. The main objective of this activity is to develop new quantum optimization, sampling, and machine learning algorithms based on quantum Markov chains.
Results
Capel, A.; Alhambra, A. M.; Gondolf, P.; Ruiz-de-Alarcón, A.; Scalet, S. O.
Conditional Independence of 1D Gibbs States with Applications to Efficient Learning Journal Article
In: Annales Henri Poincaré, 2026.
Abstract | Links | BibTeX | Tags: UCM-4.3
@article{nokey,
title = {Conditional Independence of 1D Gibbs States with Applications to Efficient Learning},
author = {Capel, A. and Alhambra, A.M. and Gondolf, P. and Ruiz-de-Alarcón, A. and Scalet, S.O.},
url = {https://link.springer.com/article/10.1007/s00023-026-01655-6},
doi = {doi.org/10.1007/s00023-026-01655-6},
year = {2026},
date = {2026-05-05},
urldate = {2026-05-05},
journal = {Annales Henri Poincaré},
abstract = {We show that spin chains in thermal equilibrium have a correlation structure in which individual regions are strongly correlated at most with their near vicinity. We quantify this with alternative notions of the conditional mutual information, defined through the so-called Belavkin–Staszewski relative entropy. We prove that these measures decay superexponentially at every positive temperature, under the assumption that the spin chain Hamiltonian is translation-invariant. Using a recovery map associated with these measures, we sequentially construct tensor network approximations in terms of marginals of small (sublogarithmic) size. As a main application, we show that classical representations of the states can be learned efficiently from local measurements with a polynomial sample complexity. We also prove an approximate factorization condition for the purity of the entire Gibbs state, which implies that it can be efficiently estimated to a small multiplicative error from a small number of local measurements. The results extend from strictly local to exponentially-decaying interactions above a threshold temperature, albeit only with exponential decay rates. As a technical step of independent interest, we show an upper bound to the decay of the Belavkin–Staszewski relative entropy upon the application of a conditional expectation.},
keywords = {UCM-4.3},
pubstate = {published},
tppubtype = {article}
}
We show that spin chains in thermal equilibrium have a correlation structure in which individual regions are strongly correlated at most with their near vicinity. We quantify this with alternative notions of the conditional mutual information, defined through the so-called Belavkin–Staszewski relative entropy. We prove that these measures decay superexponentially at every positive temperature, under the assumption that the spin chain Hamiltonian is translation-invariant. Using a recovery map associated with these measures, we sequentially construct tensor network approximations in terms of marginals of small (sublogarithmic) size. As a main application, we show that classical representations of the states can be learned efficiently from local measurements with a polynomial sample complexity. We also prove an approximate factorization condition for the purity of the entire Gibbs state, which implies that it can be efficiently estimated to a small multiplicative error from a small number of local measurements. The results extend from strictly local to exponentially-decaying interactions above a threshold temperature, albeit only with exponential decay rates. As a technical step of independent interest, we show an upper bound to the decay of the Belavkin–Staszewski relative entropy upon the application of a conditional expectation.
Giordano, S.; Martin-Delgado, M. A.
Quantum Algorithm for Testing Graph Completeness Journal Article
In: Annals of Physics, 2026.
Abstract | Links | BibTeX | Tags: UCM-4.3
@article{nokey,
title = {Quantum Algorithm for Testing Graph Completeness},
author = {Giordano, S. and Martin-Delgado, M.A.
},
url = {https://www.sciencedirect.com/science/article/pii/S0003491625003872?via%3Dihub},
doi = {doi.org/10.1016/j.aop.2025.170305},
year = {2026},
date = {2026-01-01},
urldate = {2024-08-16},
journal = {Annals of Physics},
abstract = {Testing graph completeness is a critical problem in computer science and network theory. Leveraging quantum computation, we present an efficient algorithm using the Szegedy quantum walk and quantum phase estimation (QPE). Our algorithm, which takes the number of nodes and the adjacency matrix as input, constructs a quantum walk operator and applies QPE to estimate its eigenvalues. These eigenvalues reveal the graph's structural properties, enabling us to determine its completeness. We establish a relationship between the number of nodes in a complete graph and the number of marked nodes, optimizing the success probability and running time. The time complexity of our algorithm is O(log² n), where n is the number of nodes of the graph, offering a clear quantum advantage over classical methods. This approach is useful in network structure analysis, evaluating classical routing algorithms, and assessing systems based on pairwise comparisons.},
keywords = {UCM-4.3},
pubstate = {published},
tppubtype = {article}
}
Testing graph completeness is a critical problem in computer science and network theory. Leveraging quantum computation, we present an efficient algorithm using the Szegedy quantum walk and quantum phase estimation (QPE). Our algorithm, which takes the number of nodes and the adjacency matrix as input, constructs a quantum walk operator and applies QPE to estimate its eigenvalues. These eigenvalues reveal the graph's structural properties, enabling us to determine its completeness. We establish a relationship between the number of nodes in a complete graph and the number of marked nodes, optimizing the success probability and running time. The time complexity of our algorithm is O(log² n), where n is the number of nodes of the graph, offering a clear quantum advantage over classical methods. This approach is useful in network structure analysis, evaluating classical routing algorithms, and assessing systems based on pairwise comparisons.
Escrig, G.; Campos, R.; Qi, H.; Martin-Delgado, M. A.
Quantum Bayesian Inference with Renormalization for Gravitational Waves Journal Article
In: The Astrophysical Journal Letters, vol. 979, iss. 2, pp. L36, 2025.
Abstract | Links | BibTeX | Tags: UCM-4.3
@article{nokey,
title = {Quantum Bayesian Inference with Renormalization for Gravitational Waves},
author = {Escrig, G. and Campos, R. and Qi, H. and Martin-Delgado, M.A. },
url = {https://iopscience.iop.org/article/10.3847/2041-8213/ada6ae},
doi = {10.3847/2041-8213/ada6ae},
year = {2025},
date = {2025-01-28},
journal = {The Astrophysical Journal Letters},
volume = {979},
issue = {2},
pages = {L36},
abstract = {Advancements in gravitational-wave (GW) interferometers, particularly the next generation, are poised to enable the detections of orders of magnitude more GWs from compact binary coalescences. While the surge in detections will profoundly advance GW astronomy and multimessenger astrophysics, it also poses significant computational challenges in parameter estimation. In this work, we introduce a hybrid quantum algorithm qBIRD, which performs quantum Bayesian inference with renormalization and downsampling to infer GW parameters. We validate the algorithm using both simulated and observed GWs from binary black hole mergers on quantum simulators, demonstrating that its accuracy is comparable to classical Markov Chain Monte Carlo methods. Currently, our analyses focus on a subset of parameters, including chirp mass and mass ratio, due to the limitations from classical hardware in simulating quantum algorithms. However, qBIRD can accommodate a broader parameter space when the constraints are eliminated with a small-scale quantum computer of sufficient logical qubits.},
keywords = {UCM-4.3},
pubstate = {published},
tppubtype = {article}
}
Advancements in gravitational-wave (GW) interferometers, particularly the next generation, are poised to enable the detections of orders of magnitude more GWs from compact binary coalescences. While the surge in detections will profoundly advance GW astronomy and multimessenger astrophysics, it also poses significant computational challenges in parameter estimation. In this work, we introduce a hybrid quantum algorithm qBIRD, which performs quantum Bayesian inference with renormalization and downsampling to infer GW parameters. We validate the algorithm using both simulated and observed GWs from binary black hole mergers on quantum simulators, demonstrating that its accuracy is comparable to classical Markov Chain Monte Carlo methods. Currently, our analyses focus on a subset of parameters, including chirp mass and mass ratio, due to the limitations from classical hardware in simulating quantum algorithms. However, qBIRD can accommodate a broader parameter space when the constraints are eliminated with a small-scale quantum computer of sufficient logical qubits.
Ortega, S. A.; Martin-Delgado, M. A.
Randomized SearchRank: A semiclassical approach to a quantum search engine Journal Article
In: Physical Review Research, 2024.
Abstract | Links | BibTeX | Tags: UCM-4.3
@article{nokey,
title = {Randomized SearchRank: A semiclassical approach to a quantum search engine},
author = {Ortega, S.A. and Martin-Delgado, M.A.},
url = {https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.6.043014},
doi = {doi.org/10.1103/PhysRevResearch.6.043014},
year = {2024},
date = {2024-10-04},
journal = {Physical Review Research},
abstract = {The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. However, this algorithm loses its functionality when the N/M ratio between the network size N and the number of marked nodes M is sufficiently large. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk. To maintain the same time complexity as the quantum SearchRank algorithm we propose a simplification of the algorithm. This new algorithm is called randomized SearchRank, since it corresponds to a quantum walk over a randomized mixed state. The performance of the SearchRank algorithms is first analyzed on an example network and then statistically on a set of different networks of increasing size and different number of marked nodes. On the one hand, to test the search ability of the algorithms, it is computed how the probability of measuring the marked nodes decreases with N/M for the quantum SearchRank, but remarkably it remains at a high value around 0.9 for our semiclassical algorithms, solving the quantum SearchRank problem. The time complexity of the algorithms is also analyzed, obtaining a quadratic speedup with respect to the classical ones. On the other hand, the ranking functionality of the algorithms has been investigated, obtaining a good agreement with the classical PageRank distribution. Finally, the dependence of these algorithms on the intrinsic PageRank damping parameter has been clarified. Our results suggest that this parameter should be below a threshold so that the execution time does not increase drastically.},
keywords = {UCM-4.3},
pubstate = {published},
tppubtype = {article}
}
The quantum SearchRank algorithm is a promising tool for a future quantum search engine based on PageRank quantization. However, this algorithm loses its functionality when the N/M ratio between the network size N and the number of marked nodes M is sufficiently large. We propose a modification of the algorithm, replacing the underlying Szegedy quantum walk with a semiclassical walk. To maintain the same time complexity as the quantum SearchRank algorithm we propose a simplification of the algorithm. This new algorithm is called randomized SearchRank, since it corresponds to a quantum walk over a randomized mixed state. The performance of the SearchRank algorithms is first analyzed on an example network and then statistically on a set of different networks of increasing size and different number of marked nodes. On the one hand, to test the search ability of the algorithms, it is computed how the probability of measuring the marked nodes decreases with N/M for the quantum SearchRank, but remarkably it remains at a high value around 0.9 for our semiclassical algorithms, solving the quantum SearchRank problem. The time complexity of the algorithms is also analyzed, obtaining a quadratic speedup with respect to the classical ones. On the other hand, the ranking functionality of the algorithms has been investigated, obtaining a good agreement with the classical PageRank distribution. Finally, the dependence of these algorithms on the intrinsic PageRank damping parameter has been clarified. Our results suggest that this parameter should be below a threshold so that the execution time does not increase drastically.
D., Pérez-García; Santilli, L.; Tierz, M
Hawking-Page transition on a spin chain Journal Article
In: Physical Review Research, vol. 6, iss. 3, pp. 033007, 2024.
Abstract | Links | BibTeX | Tags: UCM-4.3
@article{nokey,
title = {Hawking-Page transition on a spin chain},
author = {Pérez-García D. and Santilli, L. and Tierz, M
},
url = {https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.6.033007},
doi = {doi.org/10.1103/PhysRevResearch.6.033007},
year = {2024},
date = {2024-07-01},
urldate = {2024-07-01},
journal = {Physical Review Research},
volume = {6},
issue = {3},
pages = {033007},
abstract = {The accessibility of the Hawking-Page transition in AdS5 through a one-dimensional (1D) Heisenberg spin chain is demonstrated. We use the random matrix formulation of the Loschmidt echo for a set of spin chains, and randomize the ferromagnetic spin interaction. It is shown that the thermal Loschmidt echo, when averaged, detects the predicted increase in entropy across the Hawking-Page transition. This suggests that a 1D spin chain exhibits characteristics of black hole physics in 4+1 dimensions. We show that this approach is equally applicable to free fermion systems with a general dispersion relation.},
keywords = {UCM-4.3},
pubstate = {published},
tppubtype = {article}
}
The accessibility of the Hawking-Page transition in AdS5 through a one-dimensional (1D) Heisenberg spin chain is demonstrated. We use the random matrix formulation of the Loschmidt echo for a set of spin chains, and randomize the ferromagnetic spin interaction. It is shown that the thermal Loschmidt echo, when averaged, detects the predicted increase in entropy across the Hawking-Page transition. This suggests that a 1D spin chain exhibits characteristics of black hole physics in 4+1 dimensions. We show that this approach is equally applicable to free fermion systems with a general dispersion relation.
Canossa, G.; Pollet, L.; Martin-Delgado, M. A.; Song, H.; Liu, K.
Exotic symmetry breaking properties of self-dual fracton spin models Journal Article
In: Physical Review Research, 2024.
Abstract | Links | BibTeX | Tags: UCM-4.3
@article{nokey,
title = {Exotic symmetry breaking properties of self-dual fracton spin models},
author = {Canossa, G. and Pollet, L. and Martin-Delgado, M.A. and Song, H. and Liu, K.},
url = {https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.6.013304},
doi = {doi.org/10.1103/PhysRevResearch.6.013304},
year = {2024},
date = {2024-03-19},
journal = {Physical Review Research},
abstract = {Fracton codes host unconventional topological states of matter and are promising for fault-tolerant quantum computation due to their large coding space and strong resilience against decoherence and noise. In this paper, we investigate the ground-state properties and phase transitions of two prototypical self-dual fracton spin models—the tetrahedral Ising model and the fractal Ising model—which correspond to error-correction procedures for the representative fracton codes of type I and type II, the checkerboard code and the Haah's code, respectively, in the error-free limit. They are endowed with exotic symmetry-breaking properties that contrast sharply with the spontaneous breaking of global symmetries and deconfinement transition of gauge theories. To show these unconventional behaviors, which are associated with subdimensional symmetries, we construct and analyze the order parameters, correlators, and symmetry generators for both models. Notably, the tetrahedral Ising model acquires an extended semilocal ordering moment, while the fractal Ising model fits into a polynomial ring representation and leads to a fractal order parameter. Numerical studies combined with analytical tools show that both models experience a strong first-order phase transition with an anomalous L^-(D-1)
},
keywords = {UCM-4.3},
pubstate = {published},
tppubtype = {article}
}
Fracton codes host unconventional topological states of matter and are promising for fault-tolerant quantum computation due to their large coding space and strong resilience against decoherence and noise. In this paper, we investigate the ground-state properties and phase transitions of two prototypical self-dual fracton spin models—the tetrahedral Ising model and the fractal Ising model—which correspond to error-correction procedures for the representative fracton codes of type I and type II, the checkerboard code and the Haah's code, respectively, in the error-free limit. They are endowed with exotic symmetry-breaking properties that contrast sharply with the spontaneous breaking of global symmetries and deconfinement transition of gauge theories. To show these unconventional behaviors, which are associated with subdimensional symmetries, we construct and analyze the order parameters, correlators, and symmetry generators for both models. Notably, the tetrahedral Ising model acquires an extended semilocal ordering moment, while the fractal Ising model fits into a polynomial ring representation and leads to a fractal order parameter. Numerical studies combined with analytical tools show that both models experience a strong first-order phase transition with an anomalous L^-(D-1)
Pérez-García, D.; Santilli, L.; Tierz, M.
Dynamical quantum phase transitions from random matrix theory Journal Article
In: Quantum, vol. 8, pp. 1271, 2024.
Abstract | Links | BibTeX | Tags: UCM-4.3
@article{nokey,
title = {Dynamical quantum phase transitions from random matrix theory},
author = {Pérez-García, D. and Santilli, L. and Tierz, M.},
url = {https://quantum-journal.org/papers/q-2024-02-29-1271/},
doi = {doi.org/10.22331/q-2024-02-29-1271},
year = {2024},
date = {2024-02-29},
journal = {Quantum},
volume = {8},
pages = {1271},
abstract = {We uncover a novel dynamical quantum phase transition, using random matrix theory and its associated notion of planar limit. We study it for the isotropic XY Heisenberg spin chain. For this, we probe its real-time dynamics through the Loschmidt echo. This leads to the study of a random matrix ensemble with a complex weight, whose analysis requires novel technical considerations, that we develop. We obtain three main results: 1) There is a third order phase transition at a rescaled critical time, that we determine. 2) The third order phase transition persists away from the thermodynamic limit. 3) For times below the critical value, the difference between the thermodynamic limit and a finite chain decreases exponentially with the system size. All these results depend in a rich manner on the parity of the number of flipped spins of the quantum state conforming the fidelity.},
keywords = {UCM-4.3},
pubstate = {published},
tppubtype = {article}
}
We uncover a novel dynamical quantum phase transition, using random matrix theory and its associated notion of planar limit. We study it for the isotropic XY Heisenberg spin chain. For this, we probe its real-time dynamics through the Loschmidt echo. This leads to the study of a random matrix ensemble with a complex weight, whose analysis requires novel technical considerations, that we develop. We obtain three main results: 1) There is a third order phase transition at a rescaled critical time, that we determine. 2) The third order phase transition persists away from the thermodynamic limit. 3) For times below the critical value, the difference between the thermodynamic limit and a finite chain decreases exponentially with the system size. All these results depend in a rich manner on the parity of the number of flipped spins of the quantum state conforming the fidelity.
