Fast quantum verification for the formulas of predicate calculus

1998/09/08 by Yuri Ozhigov, Ozhigov, Yuri · 1 citation
Computer Science · Physics and Astronomy · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/9809015

Reference to the work quant-ph/9802040 with the similar result is added

openalex publication_date 1998/09/08 · arxiv created 1998/09/23 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Quantum algorithm is constructed which verifies the formulas of predicate calculus in time O(√ N) with bounded error probability, where N is the time required for classical algorithms. This algorithm uses the polynomial number of simultaneous oracle queries. This is a modification of the result of Buhrman, Cleve and Wigderson quant-ph/9802040.

Citations

• Quantum theory, the Church–Turing principle and the universal quantum computer

Cited by

• An Introduction to Quantum Complexity Theory

Related

• Verified Compilation of Quantum Oracles
• Classical Verification of Quantum Computations
• Exact quantum query complexity of EXACT and THRESHOLD
• Exact Quantum Query Algorithm for Error Detection Code Verification
• A New Quantum Lower Bound Method, with Applications to Direct Product Theorems and Time-Space Tradeoffs