Quantum Turing Machines and Quantum Prover-Verifier Interactions
Notice bibliographique
Résumé
We present results on quantum Turing machines and on prover-verifier interactions. \n \n \nIn our work on quantum Turing machines, we continue the line of research opened by Yao (1993), who proved that quantum Turing machines and quantum circuits are polynomially equivalent computational models: t ≥ n steps of a quantum Turing machine running on an input of length n can be simulated by a uniformly generated family of quantum circuits with size quadratic in t, and a polynomial-time uniformly generated family of quantum circuits can be simulated by a quantum Turing machine running in polynomial time. We then first revisit the simulation of quantum Turing machines with uniformly generated quantum circuits, and present a variation on the simulation method employed by Yao together with an analysis of it. This analysis reveals that the simulation of quantum Turing machines can be performed by quantum circuits having depth linear in t, rather than quadratic depth, and can be extended easily to many variants of quantum Turing machines, such as ones having multi-dimensional tapes. Our analysis is based on an extension of a method of Arrighi, Nesme, and Werner (2011) that allows for the localization of causal unitary evolutions, involving abstract lemmas that might be of independent interest. \n \n \nWe also consider the more complex extension of our variant to the circuit simulation of multi-tape quantum Turing machines, where our variant provides a circuit with O(t^k) size and O(t^{k-1}) depth for the simulation of t steps of a machine with k tapes. This can be contrasted with the O(t^{k}) depth corresponding to the generalization of Yao's simulation by Nishimura and Ozawa (2002). Our usage of abstract techniques regarding the localization of causal unitary evolutions allows again for a simplification of the algebraic manipulation aspects of the construction. We also discuss the further extension to the case of oracle quantum Turing machines. \n \n \nIn our work on prover-verifier interactions, we first consider a protocol under the name of perfect/conclusive quantum state exclusion. This means to be able to discard with certainty at least one out of n possible quantum state preparations by performing a measurement of the resulting state. When all the preparations correspond to pure states and there are no more of them than their common dimension, it is an open problem whether POVMs give any additional power for this task with respect to projective measurements. This is the case even for the simple case of three states in three dimensions, which is discussed by Caves, Fuchs and Schack (2002) as unsuccessfully tackled. In our work, we give an analytical proof that in this case POVMs do indeed not give any additional power with respect to projective measurements. We also discuss possible generalizations of our work, including an application of Quadratically Constrained Quadratic Programming that might be of special interest. \n \n \nWe additionally consider the problem of quantum hedging, a particular kind of quantum correlation that arises between parallel instances of prover-verifier interactions. M. and Watrous (2012) studied a protocol that exhibited a perfect form of quantum hedging, where the risk for the prover of losing a first game can completely offset the corresponding risk for a second game. We take a step towards a better understanding of this hedging phenomenon by giving a characterization of the prover's optimal behavior for a natural generalization of this protocol. Furthermore, we discuss how the usage of the logarithmic utility principle to analyze prover-verifier interactions could justify further study of quantum hedging.
Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.
Comment cette classification a été obtenuedéplier
Prédiction machine sur la base complète
Imitation des enseignantsNi prévalence calibrée, ni vérité terrain. Validation humaine à venir. Le volet Gemma est une étiquette directe du modèle pour chaque travail de la base, lue sur la notice réduite au titre. Le volet Codex est un classifieur appris des 10 348 étiquettes directes de Codex et calibré sur les taux pondérés de l'échantillon; les champs sans appui suffisant ne portent aucun appel Codex. Le mode candidate est l'union des deux volets; le consensus est leur intersection. Ces sorties portent le statut machine_predicted_unvalidated et ne sont pas des étiquettes humaines.
Scores du classifieur distillé par catégorie (deux têtes)
| Catégorie | Codex | Gemma |
|---|---|---|
| Métarecherche | 0,003 | 0,014 |
| Méta-épidémiologie (sens strict) | 0,001 | 0,001 |
| Méta-épidémiologie (sens large) | 0,001 | 0,003 |
| Bibliométrie | 0,001 | 0,002 |
| Études des sciences et des technologies | 0,003 | 0,006 |
| Communication savante | 0,003 | 0,013 |
| Science ouverte | 0,003 | 0,006 |
| Intégrité de la recherche | 0,003 | 0,006 |
| Charge utile insuffisante (le modèle a refusé de juger) | 0,024 | 0,002 |
Scores machine (provisoires)
Les deux têtes enseignantes du modèle étudiant, lues sur ce travail. Un score ordonne la base pour la relecture; il n'affirme jamais une catégorie, et le statut de validation accompagne chaque rangée tel quel.
Scores de référence d'un modèle non mature (critères de maturité non atteints, 7 itérations). Un score ordonne; il n'affirme jamais une catégorie.
score_only:v0-immature-baseline · tel quel depuis la passe de notation : score_only signifie que le nombre peut ordonner les travaux, et qu'aucune étiquette de catégorie n'en découleClassification
machine, non validéePrédiction automatique; un appel candidat d’une seule source (Gemma direct ou Codex distillé), pas un consensus.
Le détail, modèle par modèle et score par score, se trouve en fin de page sous « Comment cette classification a été obtenue ».