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 Working paper
2025.
Abstract | Links | BibTeX | Tags: UCM-4.3
@workingpaper{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://doi.org/10.48550/arXiv.2402.18500},
doi = {doi.org/10.48550/arXiv.2402.18500},
year = {2025},
date = {2025-12-02},
urldate = {2025-12-02},
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 = {workingpaper}
}
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.
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.
Giordano, S.; Martin-Delgado, M. A.
Quantum Algorithm for Testing Graph Completeness Working paper
2024.
Abstract | Links | BibTeX | Tags: UCM-4.3
@workingpaper{nokey,
title = {Quantum Algorithm for Testing Graph Completeness},
author = {Giordano, S. and Martin-Delgado, M.A.
},
url = {https://arxiv.org/abs/2407.20069},
doi = {doi.org/10.48550/arXiv.2407.20069},
year = {2024},
date = {2024-08-16},
urldate = {2024-08-16},
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 , where 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 = {workingpaper}
}
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 , where 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.
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.
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.
