Aplicación
Algoritmos de cadenas de Markov cuánticas
GICC + MATHQI
Descripción del grupo:
La Universidad Complutense de Madrid (UCM) cuenta con dos grupos de investigación expertos en computación cuántica, QICC y MATHQI, y le interesa colaborar con los demás socios del proyecto para el desarrollo, expansión y difusión de esta tecnología. Con el fin de progresar en la investigación de la computación cuántica en los campos de su interés científico, la UCM desarrollará las actividades descritas en el siguiente apartado, dentro del marco del proyecto Quantum Spain.
Los grupos QICC y MATHQI, liderados respectivamente por los profesores Miguel Ángel Martín-Delgado y David Pérez-García, cuentan con una amplia experiencia en el análisis matemático de conceptos relacionados con la computación cuántica, así como en la simulación de sistemas cuánticos con redes de tensores. Las tareas de estos grupos de investigación de la UCM se centrarán en el estudio de las redes de tensores y el uso de cadenas de Markov cuánticas en procesos relacionados con la inteligencia artificial.
Descripción de la actividad:
Los algoritmos de cadena de Markov cuánticos son métodos estocásticos para reproducir distribuciones de probabilidad, que presentan ventajas de convergencia sobre equivalentes clásicos. Estas cadenas han demostrado su utilidad en optimización de un problema complejo: el plegado de proteínas. El objetivo principal de esta actividad es desarrollar nuevos algoritmos cuánticos de optimización, muestreo y aprendizaje automático basados en cadenas de Markov cuánticas.
Resultados
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 Artículo de revista
En: Annales Henri Poincaré, 2026.
Resumen | Enlaces | BibTeX | Etiquetas: 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 Artículo de revista
En: Annals of Physics, 2026.
Resumen | Enlaces | BibTeX | Etiquetas: 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 Artículo de revista
En: The Astrophysical Journal Letters, vol. 979, iss. 2, pp. L36, 2025.
Resumen | Enlaces | BibTeX | Etiquetas: 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 Artículo de revista
En: Physical Review Research, 2024.
Resumen | Enlaces | BibTeX | Etiquetas: 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 Artículo de revista
En: Physical Review Research, vol. 6, iss. 3, pp. 033007, 2024.
Resumen | Enlaces | BibTeX | Etiquetas: 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 Artículo de revista
En: Physical Review Research, 2024.
Resumen | Enlaces | BibTeX | Etiquetas: 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 Artículo de revista
En: Quantum, vol. 8, pp. 1271, 2024.
Resumen | Enlaces | BibTeX | Etiquetas: 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.
