Concurrent semantics for probabilistic and quantum languages

dc.commentsEE/2026/3487
dc.contributor.advisorBarbosa, Luís Nuno Sousa Martinho Soares
dc.contributor.advisorNeves, Renato Jorge Araújo
dc.contributor.authorFernandes, Vítor Emanuel Gonçalves
dc.date.accessioned2026-07-06T13:54:05Z
dc.date.issued2026-06-20
dc.date.submitted2025-12
dc.description.abstractThis 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.abstractEsta 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.sponsorshipThis 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.tid101657498
dc.identifier.urihttps://hdl.handle.net/1822/102485
dc.language.isoeng
dc.relationTiming Constraints in Quantum Programming Languages [2020.05715.BD]
dc.rightsopenAccess
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectConcurrency
dc.subjectProbabilistic programming
dc.subjectQuantum programming
dc.subjectProgram semantics
dc.subjectHaskell
dc.subjectConcorrência
dc.subjectProgramação probabilística
dc.subjectProgramação quântica
dc.subjectSemântica de programas
dc.subject.fosCiências Naturais::Ciências da Computação e da Informação
dc.titleConcurrent semantics for probabilistic and quantum languageseng
dc.typedoctoralThesis
dspace.entity.typePublication
oaire.awardNumber2020.05715.BD
oaire.awardTitleTiming Constraints in Quantum Programming Languages [2020.05715.BD]
oaire.awardURIhttps://hdl.handle.net/1822/102483
oaire.funderIdentifierhttp://doi.org/10.13039/501100001871
oaire.funderNameFundação para a Ciência e a Tecnologia, I.P.
relation.isProjectOfPublication6b89cd11-1041-4b15-b8b8-b51727fe1e79
relation.isProjectOfPublication.latestForDiscovery6b89cd11-1041-4b15-b8b8-b51727fe1e79
sdum.degree.gradeMuito bom
sdum.uoeiEscola de Engenharia
thesis.degree.grantorUniversidade do Minhopor
thesis.degree.nameDoutoramento em Informática

Ficheiros

Pacote original

A mostrar 1 - 1 de 1
A carregar...
Nome:
Vitor Emanuel Goncalves Fernandes.pdf
Tamanho:
2.28 MB
Formato:
Adobe Portable Document Format