6 papers
QMA has perfect completeness
Sabee Grewal, Dorian Rudolph
We prove , i.e., every quantum Merlin-Arthur proof system can be made perfectly complete. Our construction uses only Hadamard, Toffoli, and gates…
Promises should be taken seriously: On relativization with promise problems
David Miloschewsky, Supartha Podder, Dorian Rudolph
Relativization is concerned with comparing computational models with black-box access to an oracle. For promise problems, black-box access is not canonical due to inputs outside of…
En Route to a Standard QMA1 vs. QCMA Oracle Separation
David Miloschewsky, Supartha Podder, Dorian Rudolph
We study the power of quantum witnesses under perfect completeness. We construct a classical oracle relative to which a language lies in but not in …
On the Pure Quantum Polynomial Hierarchy and Quantified Hamiltonian Complexity
Sabee Grewal, Dorian Rudolph
We prove several new results concerning the pure quantum polynomial hierarchy (pureQPH). First, we show that QMA(2) is contained in pureQSigma2, that is, two unentangled existentia…
On the Complexity of Pure-State Consistency of Local Density Matrices
Jonas Kamminga, Dorian Rudolph
In this work we investigate the computational complexity of the pure consistency of local density matrices (PureCLDM) and pure N-representability (Pure-N-Representability; analog o…
Towards a universal gateset for
Dorian Rudolph
is with perfect completeness, i.e., the prover must accept with a probability of exactly in the YES-case. Whether and $\mathsf{…