Total functions in QMA

DOI10.1007/s11128-020-02959-0OpenAlexW2798565120MaRDI QIDQ2684235

Serge Massar, Miklos Santha

Publication date: 16 February 2023

Published in: Quantum Information Processing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.00670

zbMATH Keywords

quantum algorithmsquantum complexitytotal functional QMAfunctional QMAquantum merlin Arthur games

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum algorithms and complexity in the theory of computing (68Q12)

Related Items (1)

Characterising the intersection of QMA and coQMA

Cites Work

• On total functions, existence theorems and computational complexity
• Quantum Arthur-Merlin games
• How easy is local search?
• On the complexity of the parity argument and other inefficient proofs of existence
• Towards a unified complexity theory of total functions
• The commuting local Hamiltonian problem on locally expanding graphs is approximable in \(\mathsf{NP}\)
• Quantum 3-SAT Is QMA$_1$-Complete
• Quantum money from knots
• EXPONENTIAL IMPROVEMENT IN PRECISION FOR SIMULATING SPARSE HAMILTONIANS
• Settling the complexity of computing two-player Nash equilibria
• A constructive proof of the general lovász local lemma
• Quantum algorithms revisited
• Strengths and Weaknesses of Quantum Computing
• A constructive proof of the Lovász local lemma
• The Complexity of Computing a Nash Equilibrium
• Quantum Lovász local lemma: Shearer’s bound is tight
• A quantum Lovász local lemma
• The Complexity of the Local Hamiltonian Problem
• On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Total functions in QMA