PhD Thesis
Hybrid quantum-classical high-performance computation
— 2025
Key information
Authors:
Supervisors:
Published in
July 30, 2025
Abstract
Nesta tese, procuramos contribuir para a compreensão do poder computacional do atual acesso a computação clássica “barata” e rápida juntamente com computação quântica limitada. Consideramos dois modelos para esta limitação: um modelo menos realista, mas mais teoricamente tratável, e um segundo modelo mais próximo de um cenário realista. Nomeadamente, consideramos primeiro, algoritmos híbridos quântico clássicos cujas sub-rotinas quânticas podem executar um determinado oráculo apenas (assimptoticamente) um número máximo de vezes. Neste contexto, estabelecemos ligações a Quantum Signal Processing (QSP), fornecendo uma nova perspetiva relativamente ao funcionamento de algumas famílias de algoritmos híbridos quântico-clássicos: estas podem ser entendidas como interpolações entre o quão informativas e “quão quânticas” são as medições preparadas. Aprofundamos a investigação desta relação, mostrando que esta visão não é completa (na medida em que não explica alguns trade-offs conhecidos), mas que é útil (na medida em que descreve um procedimento sistemático que, por vezes, basta para recuperar os melhores resultados conhecidos). O segundo modelo considerado é o da computação clássica coordenada com computação quântica de tempo (assimptoticamente) limitado. Este modelo é mais realista do que o modelo oracular, ainda que menos realista do que uma modelação directa de ruído. Por outro lado, este modelo tem em conta o tempo de execução quântico e clássico (desconsiderado pelo modelo de oráculo). Encarando esta situação como uma na qual é possível preparar e medir determinados estados quânticos e processar as medições classicamente, estabelecemos ligações a Quantum Singular Value Transformations (QSVTs; uma generalização de QSP), e, em particular, a resultados existentes sobre a desquantização de QSVTs em contexto clássico. Fazendo-o, estabelecemos limites melhorados à complexidade da estimação distribuída do produto interno, dando prospectivamente um primeiro passo numa interpolação quântica-clássica de QSVTs na sua generalidade. Globalmente, mostramos que QSP e suas generalizações parecem ser ferramentas promissoras para o raciocínio formal sobre algoritmos híbridos quântico-clássicos. In this thesis, we seek to contribute to the understanding of the computational power of the current technological setup, i.e., “cheap” and fast classical computation coordinated with limited quantum computation. We consider two models for this limitation: the first is more theoretically tractable, while the second approaches a more realistic setting. Namely, we first consider hybrid quantum-classical algorithms where the quantum subroutines may only call a certain oracle a maximum (asymptotic) number of times. In this context, we draw connections to the framework of Quantum Signal Processing (QSP). In doing so, we establish a new perspective for some quantum-classical hybrid algorithm families: that these follow from a compromise between how informative and “how quantum” a measurement is. We further investigate this relationship, showing that this perspective is not complete (it does not explain some known trade-offs) but that it is useful (it outlines a systematic procedure which sometimes recover the best-known bounds). The second model we consider is of classical computation coordinated with (asymptotic) time-limited quantum computation. This model moves towards a more realistic setting, while not being as realistic as noise-modelling. On the other hand, our analysis of this setting considers both the quantum and the classical running time (which the query-model disregarded). By phrasing this setup as the ability to prepare and measure quantum states, and then post-process this information classically, we again draw connections to Quantum Singular Value Transformations (QSVTs; a generalization of QSP). In particular, we connect existing dequantization results to this setup. In doing so, we improve some known results on the complexity of distributed inner product estimation, while also hoping to provide a first step towards a quantum-classical interpolation of QSVTs. Overall, we show that the frameworks of QSP and generalizations seem to be promising tools for formally reasoning about hybrid quantum-classical algorithms.
Publication details
Authors in the community:
Supervisors of this institution:
Yasser Rashid Revez Omar
ist30513
RENATES TID
101690193
Degree Name
Doutoramento em Física
Fields of Science and Technology (FOS)
physical-sciences - Physical sciences
Keywords
- Quantum algorithms
- Hybrid quantum-classical algorithms
- Hybrid oracle complexity
- Quantum signal processing
- Sample and query
- Algoritmos quânticos
- Computação quântica-clássica híbrida
- Complexidade oracular híbrida
Publication language (ISO code)
eng - English
Rights type:
Only metadata available
Institution name
Instituto Superior Técnico
Financing entity
Fundação para a Ciência e a Tecnologia
Identifier for the funding entity: https://doi.org/10.13039/501100001871
Type of identifier of the funding entity: Crossref Funder
Number for the project, award or grant: 2021.05528.BD