Quantum multi-prover interactive proof systems with limited prior entanglement.

DOI10.1016/S0022-0000(03)00035-7MaRDI QIDQ1401955zbMATH OpenFDO

Authors Hirotada Kobayashi, Keiji Matsumoto

Publication date 19 August 2003

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-0000(03)00035-7

zbMATH Keywords

Computational complexityInteractive proof systemsQuantum computing

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68)

Recommendations

• scientific article; zbMATH DE number 1979492
• Using entanglement in quantum multi-prover interactive proofs
• Constant-space quantum interactive proofs against multiple provers
• Quantum multiprover interactive proofs with communicating provers
• A multiprover interactive proof system for the local Hamiltonian problem (extended abtract)

Cites work

• A new universal and fault-tolerant quantum basis
• Algebraic methods for interactive proof systems
• Fully parallelized multi-prover protocols for NEXP-time
• Games against nature
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 1775384 (Why is no real title available?)
• IP = PSPACE
• Non-deterministic exponential time has two-prover interactive protocols
• On the power of multi-prover interactive protocols
• Parallel transport and ``quantum holonomy along density operators
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• PSPACE has constant-round quantum interactive proof systems
• PSPACE is provable by two provers in one round
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Strengths and Weaknesses of Quantum Computing
• The Knowledge Complexity of Interactive Proof Systems

Cited in

(22)

• An application of quantum finite automata to interactive proof systems
• Parallelization of entanglement-resistant multi-prover interactive proofs
• Constant-space quantum interactive proofs against multiple provers
• Rank-one quantum games
• Quantum de Finetti theorems under local measurements with applications
• On the power of quantum, one round, two prover interactive proof systems
• Quantum proofs
• A multiprover interactive proof system for the local Hamiltonian problem (extended abtract)
• Entanglement-resistant two-prover interactive proof systems and non-adaptive PIR's
• Quantum multiprover interactive proofs with communicating provers
• Interactive proofs with approximately commuting provers
• scientific article; zbMATH DE number 1979492 (Why is no real title available?)
• Algorithms and Computation
• ON THE POWER QUANTUM COMPUTATION OVER REAL HILBERT SPACES
• Quantum Merlin-Arthur proof systems: are multiple Merlins more helpful to Arthur?
• On quantum interactive proofs with short messages
• scientific article; zbMATH DE number 6292749 (Why is no real title available?)
• Entanglement in Interactive Proof Systems with Binary Answers
• STACS 2005
• Using entanglement in quantum multi-prover interactive proofs
• The role of piracy in quantum proofs
• Quantum delegation with an off-the-shelf device

This page was built for publication: Quantum multi-prover interactive proof systems with limited prior entanglement.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401955)