Quantum deduction rules (Q1001909)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Quantum deduction rules
scientific article

    Statements

    Quantum deduction rules (English)
    0 references
    0 references
    19 February 2009
    0 references
    This well-written paper deals with many of the important capabilities and limitations of quantum systems for high-speed theorem-proving for propositional logic. Of course, advances in such areas will likely lead to improvements over classical high-speed (1) communication systems, (2) cryptosystems, and (3) computation systems. The reviewer believes the author is very optimistic to suggest that his interesting results can be extended to predicate logic, in general, without special provisos. The author's results may well extend to first-order predicate logic, but not to higher-order predicate logics, due to the presence of various recursively unsolvable problems; e.g., in second-order axiomatic arithmetic, \(A^2\). The author's main achievement is the elegant extension of the classical concept of the Cook-Reckhow Frege System (CRFS) to a useful quantum analogue of CRFS. Finally, the author poses two challenging problems and a conjecture on the existence of a universal quantum Frege system. The reviewer looks forward to seeing the author's novel methods and approaches applied to many-valued logics and modal logics.
    0 references
    quantum computation
    0 references
    proof complexity
    0 references
    quantum Frege proof systems
    0 references
    propositional logic
    0 references
    quantum cryptosystems
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references