Source-linked AI summary
On the completeness of quantum computation models
Pablo Arrighi, Gilles Dowek
TL;DR
Computability over infinite-dimensional spaces can depend on the chosen indexing, complicating an absolute notion of completeness for quantum computation models. The paper studies stability when tensor product is included among the computable operations. It concludes that finite tensorial dimension is the relevant criterion for quantum spaces, and that such spaces are probably sufficient to express all quantum algorithms.
Problem
Computability over infinite-dimensional vector spaces can vary with the indexing, making an indexing-independent notion of completeness for quantum computation models a challenge.
Source: §1 · p. 2Method
The paper investigates admissible indexings that make tensor product computable and derives stability results for vector spaces and specified finite-degree field extensions.
Source: §1 · p. 2, §5 · pp. 11–12Results
Finite tensorial dimension, rather than vector-space dimension, is the relevant criterion, and such spaces are probably sufficient to express all quantum algorithms.
Source: §7 · p. 13Takeaways & Limitations
For a physical system with stable computability, its dynamics can be assessed as computable, universal, or uncomputable, giving a formal way to consider the Church-Turing thesis in quantum theory.
Source: §7 · p. 14For field extensions, the paper restricts to extensions of Q because its stability proof requires the base field to be effectively enumerable within the extension.
Source: §5 · p. 12
Abstract
from arXiv · showhide
The notion of computability is stable (i.e. independent of the choice of an indexing) over infinite-dimensional vector spaces provided they have a finite "tensorial dimension". Such vector spaces with a finite tensorial dimension permit to define an absolute notion of completeness for quantum computation models and give a precise meaning to the Church-Turing thesis in the framework of quantum theory. (Extra keywords: quantum programming languages, denotational semantics, universality.)
1 Introduction
Classical circuit models handle fixed-size Boolean inputs and outputs, while quantum models also address unbounded-size data. The paper argues that tensor products can help make computability stable over infinite-dimensional spaces, providing a basis for defining completeness for quantum computation models.
1 Introduction
- Quantum circuit models handle fixed-size inputs and outputs, while models such as quantum Turing machines and quantum λ-calculi can express algorithms over unbounded-size data.Completeness for such models requires first defining a set of computable quantum functions.Source: §1 · pp. 1–2
- For arbitrary countable sets, computability can depend on the indexing, so naive completeness for a quantum model may be indexing-relative.The Church-Turing thesis reflects robustness over the natural numbers, but that robustness does not automatically extend to countable vector spaces.Source: §1 · p. 2
- Making vector-space operations computable does not ensure stable computability in infinite-dimensional spaces, because a non-computable basis permutation can change the computable functions.The paper notes that observing measurement probabilities rather than state vectors does not avoid the issue, since uncomputable amplitudes can still be read probabilistically.Source: §1 · p. 2
- Adding tensor product as a primitive operation and requiring it to be computable can make computability stable despite infinite dimension.The paper derives this result from a general result about extensions of algebraic structures that preserve stable computability.Source: §1 · pp. 2–3
2 Stable computability
This section develops computability over indexed sets and structures, then uses admissible indexings to define stability and show when computable functions are independent of indexing choices.
2 Stable computability
- Finite trees labeled by a finite set can be indexed recursively, and the resulting tree indexing is independent of how the labels themselves are indexed.The section also uses effective enumerability and a computable right-inverse result for surjective partial computable functions between effectively enumerable sets.Source: §2 · p. 3
2.1 Indexings
- An indexing is a surjective partial map from natural-number codes with effectively enumerable domain and decidable equality of represented elements.A structure's indexing is admissible when its operations are computable relative to the indexings of their domains and codomains.Source: §2.1 · pp. 3–4
2.2 Stability
- Stable computability requires computable translations between admissible indexings, and then the computable functions on associated sets are independent of those indexing choices.Proposition 2 establishes this independence, while Proposition 3 gives a converse criterion for stability.Source: §2.2 · pp. 4–5
3 Relative finite generation
Relative finite generation provides a sufficient condition for stable computability when a structure is added to a structure that already has stable computability. It generalizes finite-dimensionality, while effective generation shows that finite generation is not necessary.
3 Relative finite generation
- Relative finite generation requires terms that cover every target element, using operations and indexed elements from a base structure.The selected term sets must be effectively enumerable, and equality of denotations must be decidable; choosing a subset can avoid harder equality tests on all terms.Source: §3 · pp. 5–6
- Finite generation generalizes finite-dimensionality, with structure dimension defined as the minimum size of a finite generative set.The definition also applies relative to an already indexed base structure.Source: §3 · pp. 6–7
- A finitely generated extension of a structure with stable computability preserves stability when the base indexing is admissible.The theorem constructs an admissible indexing of the extension and proves stability for the combined structure.Source: §3 · pp. 7–8
- Computability is stable for the natural-number structures ⟨N, S⟩ and ⟨N, +⟩, and for ⟨Q, +, −, ×, /⟩.For these examples, terms cover every element and equality of denotations is decidable.Source: §3 · p. 8
- Finite generation is sufficient but not necessary for stability: ⟨Q, +, ×⟩ is stable despite not being finitely generated.Subtraction and division can be effectively defined from addition and multiplication.Source: §3 · p. 9
- Effective generation can characterize stable computability using an enumerable expression language, surjective denotation, decidable equality, and effective operation construction.The paper states that this approach makes stability and effective generation equivalent.Source: §3 · p. 9
4 Vector spaces
For vector spaces, stable computability is characterized by stability of the scalar field and finite dimension. In particular, finite-dimensional spaces over stable fields are stable, whereas infinite-dimensional spaces are not.
4 Vector spaces
- A finite-dimensional vector space over a field with stable computability has stable computability.Vectors can be represented by terms using a finite basis and indexed scalar coefficients, with equality decidable through scalar equality.Source: §4 · p. 10
- Vector-space computability is stable if and only if the scalar field is stable and the space is finite-dimensional.Thus, stability fails for an infinite-dimensional space even when its field is stable.Source: §4 · p. 10
- If the field is unstable, its instability carries over to the vector space when the dimension is finite or countable.The proof encodes scalar indexings as basis-coordinate representations.Source: §4 · p. 10
- For countably infinite dimension over a stable field, a noncomputable permutation of basis vectors contradicts stable computability.The proof uses such a permutation to construct a noncomputable function from a hypothetical computable translation between indexings.Source: §4 · pp. 10–11
5 Field extensions
Computability stability extends from a field to structures built from finite-degree field extensions. For extensions of the rationals, the paper also establishes stability of the extension field itself, relying on effective enumerability of the base field.
5 Field extensions
- Finite-degree extensions preserve stability over the structure combining K and L with scalar operations, and also when L’s multiplication is included.The field L must be an extension of finite degree of K.Source: §5 · p. 11
- A basis of L over K represents its elements as finite sums of K-scalars times basis vectors, enabling computable operations on indexed terms.The construction uses the finite basis and structure coefficients for multiplication in L.Source: §5 · pp. 11–12
- For stability of L itself, the paper restricts to finite-degree extensions of Q because K must be effectively enumerable within L, as holds when K is Q.Proposition 11 concludes that computability is stable over any finite-degree extension of Q.Source: §5 · p. 12
- For an arbitrary admissible indexing, the proof shows that the indices of Q are effectively enumerable, then uses this to compare admissible indexings.It constructs a computable enumeration from indices for 0 and 1 and the operations of the structure.Source: §5 · p. 12
6 Tensor spaces
Infinite data types can be finitely generated through their operations, but infinite-dimensional vector spaces alone need not have stable computability. The paper obtains stability for tensor spaces whose basis vectors are generated from a finite set using tensor products.
6 Tensor spaces
- Infinite-dimensional vector spaces lack stable computability when their basis vectors are unrelated, while adding suitable generation operations addresses this problem for infinite data types.The paper compares successor for natural numbers and cons or tree-building operations for structured data.Source: §6 · pp. 12–13
- A tensor space has stable computability when its basis consists of iterated tensor products of elements from a finite subset, assuming stability over the scalar field.The tensor product is bilinear and serves as the operation generating the basis vectors.Source: §6 · p. 13
- The proof represents vectors as denotations of terms built from scalars and tensor products, then uses decidable scalar equality to decide equality of terms.This makes the tensor-space structure finitely generated relative to the field, so field stability yields stability for the full structure.Source: §6 · p. 13
7 Conclusion
The paper establishes stable computability for several algebraic structures, including tensor spaces that may be infinite-dimensional as vector spaces. It argues that finite tensorial dimension is relevant to quantum data and provides a framework for examining whether physical dynamics respect or break the Church-Turing thesis.
7 Conclusion
- Stable computability holds for finite-degree extensions of Q, finite-dimensional vector spaces over such fields, and tensor spaces finite-dimensional as tensor spaces, even when infinite-dimensional as vector spaces.The conclusion contrasts this robustness with the indexing dependence of other countable domains.Source: §7 · p. 13
- For quantum computing, finite tensorial dimension—not finite vector-space dimension—is the relevant notion because tensor products handle finite generation of data types.The paper says such spaces over finite-degree extensions of Q are probably sufficient to express all quantum algorithms.Source: §7 · p. 13
- Whether these spaces suffice for all quantum physics depends on decomposing systems with infinitely many basis states into finite but potentially unbounded numbers of finite-state subsystems.Source: §7 · p. 13
- Stable computability lets one assess whether a physical system’s dynamics are computable, universal, or uncomputable, giving a formal way to ask whether they respect or break the Church-Turing thesis.Source: §7 · p. 14