Concurrent semantics for probabilistic and quantum languages
| dc.comments | EE/2026/3487 | |
| dc.contributor.advisor | Barbosa, Luís Nuno Sousa Martinho Soares | |
| dc.contributor.advisor | Neves, Renato Jorge Araújo | |
| dc.contributor.author | Fernandes, Vítor Emanuel Gonçalves | |
| dc.date.accessioned | 2026-07-06T13:54:05Z | |
| dc.date.issued | 2026-06-20 | |
| dc.date.submitted | 2025-12 | |
| dc.description.abstract | This thesis explores both theoretical and practical aspects of concurrent programming languages that integrate probabilistic and/or quantum computations. On the theoretical side, we investigate how event structures, a model for concurrency, can be used to furnish concurrent languages with denotational semantics. Event structures are studied in three distinct settings: non-deterministic, probabilistic, and quantum computation. Based on these three realms, we successively extend a core imperative-like concurrent language with non-deterministic choice, probabilistic choice, and standard quantum operations. For each extension, we define both operational and denotational semantics and establish their equivalence through soundness and adequacy results. Soundness ensures that every behavior obtainable through the operational semantics is reflected denotationally, showing that the denotational semantics correctly abstracts the computations. Conversely, adequacy guarantees that whenever the denotational semantics yields a value, this value can be produced by the operational semantics, demonstrating that the operational semantics explicitly realises what the denotational semantics predicts. On the practical side, motivated by the growing interplay between classical and quantum computers, we integrate non-deterministic choice, probabilistic choice, and quantum operations into a single language, further extended with a synchronization primitive. We develop an interpreter for this language and test it on several illustrative examples, including three versions of the Dining Philosophers problem: concurrentonly, probabilistic, and quantum. Using our tool, we demonstrate that a result stated in the literature about the quantum Dining Philosophers problem does not hold, leaving open the question of whether an efficient algorithm for solving it exists. | eng |
| dc.description.abstract | Esta tese explora tanto os aspectos teóricos como os prácticos de linguagens de programação concorrentes que integram computações probabilísticas e/ou quânticas. Do ponto de vista teórico, investigámos de que forma event structures, um modelo para concorrência, podem ser utilizadas para equipar linguagens concorrentes com uma semântica denotacional. As event structures são estudadas em três contextos distintos: computação não determinística, probabilística e quântica. Com base nestes três domínios, estendemos sucessivamente uma linguagem concorrente do género imperativa com a escolha não determinística, a escolha probabilística e operações quânticas usuais. Para cada extensão, definimos tanto a semântica operacional como a semântica denotacional, e estabelecemos a sua equivalência através de resultados de soundness e adequacy. Soundness garante que cada comportamento obtido através da semântica operacional é refletido denotacionalmente, mostrando que a semântica denotacional abstrai correctamente as computações. Por outro lado, adequacy assegura que, sempre que a semântica denotacional produz um valor, esse valor pode ser obtido pela semântica operacional, demonstrando que a semântica operacional concretiza explicitamente o que a semântica denotacional prevê. Do ponto de vista prático, motivados pela crescente interação entre computadores clássicos e quânticos, integramos a escolha não determinística, a escolha probabilística e operações quânticas numa única linguagem, posteriormente estendida com uma primitiva de sincronização. Desenvolvemos um interpretador para esta linguagem e testámo-lo com vários exemplos ilustrativos, incluindo três versões do problema dos Dining Philosophers: apenas concorrente, probabilística e quântica. Com o auxílio da nossa ferramenta, demonstrámos que um resultado apresentado na literatura sobre a versão quântica do problema dos Dining Philosophers não se verifica, deixando em aberto a questão sobre a existência de um algoritmo eficiente para o resolver. | por |
| dc.description.sponsorship | This work was financed by National Funds through the FCT - Fundação para a Ciência e a Tecnologia, I.P. (Portuguese Foundation for Science and Technology), under the scope of a Ph.D. Grant with reference 2020.05715.BD. | |
| dc.identifier.tid | 101657498 | |
| dc.identifier.uri | https://hdl.handle.net/1822/102485 | |
| dc.language.iso | eng | |
| dc.relation | Timing Constraints in Quantum Programming Languages [2020.05715.BD] | |
| dc.rights | openAccess | |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| dc.subject | Concurrency | |
| dc.subject | Probabilistic programming | |
| dc.subject | Quantum programming | |
| dc.subject | Program semantics | |
| dc.subject | Haskell | |
| dc.subject | Concorrência | |
| dc.subject | Programação probabilística | |
| dc.subject | Programação quântica | |
| dc.subject | Semântica de programas | |
| dc.subject.fos | Ciências Naturais::Ciências da Computação e da Informação | |
| dc.title | Concurrent semantics for probabilistic and quantum languages | eng |
| dc.type | doctoralThesis | |
| dspace.entity.type | Publication | |
| oaire.awardNumber | 2020.05715.BD | |
| oaire.awardTitle | Timing Constraints in Quantum Programming Languages [2020.05715.BD] | |
| oaire.awardURI | https://hdl.handle.net/1822/102483 | |
| oaire.funderIdentifier | http://doi.org/10.13039/501100001871 | |
| oaire.funderName | Fundação para a Ciência e a Tecnologia, I.P. | |
| relation.isProjectOfPublication | 6b89cd11-1041-4b15-b8b8-b51727fe1e79 | |
| relation.isProjectOfPublication.latestForDiscovery | 6b89cd11-1041-4b15-b8b8-b51727fe1e79 | |
| sdum.degree.grade | Muito bom | |
| sdum.uoei | Escola de Engenharia | |
| thesis.degree.grantor | Universidade do Minho | por |
| thesis.degree.name | Doutoramento em Informática |
Ficheiros
Pacote original
1 - 1 de 1
A carregar...
- Nome:
- Vitor Emanuel Goncalves Fernandes.pdf
- Tamanho:
- 2.28 MB
- Formato:
- Adobe Portable Document Format