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
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