211 citations · 1.2k across the 74 of their papers we have counts for
6 papers · 2 filters
Measuring 4-local n-qubit observables could probabilistically solve PSPACE
Pawel Wocjan, Dominik Janzing, Thomas Decker +1
We consider a hypothetical apparatus that implements measurements for arbitrary 4-local quantum observables A on n qubits. The apparatus implements the ``measurement algorithm'' af…
Two QCMA-complete problems
Pawel Wocjan, Dominik Janzing, Thomas Beth
QMA and QCMA are possible quantum analogues of the complexity class NP. In QCMA the verifier is a quantum program and the proof is classical. In contrast, in QMA the proof is also…
Identity check is QMA-complete
Dominik Janzing, Pawel Wocjan, Thomas Beth
We define the problem identity check: Given a classical description of a quantum circuit, determine whether it is almost equivalent to the identity. Explicitly, the task is to deci…
Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete
Dominik Janzing, Pawel Wocjan, Thomas Beth
We introduce the quantum complexity class FQMA. This class describes the complexity of generating a quantum state that serves as a witness for a given QMA problem. In a certain sen…
Treating the Independent Set Problem by 2D Ising Interactions with Adiabatic Quantum Computing
Pawel Wocjan, Dominik Janzing, Thomas Beth
We construct a nearest-neighbor Hamiltonian whose ground states encode the solutions to the NP-complete problem INDEPENDENT SET in cubic planar graphs. The Hamiltonian can be easil…
The 2-local Hamiltonian problem encompasses NP
Pawel Wocjan, Thomas Beth
We show that the NP complete problems MAX CUT and INDEPENDENT SET can be formulated as the 2-local Hamiltonian problem as defined by Kitaev. He introduced the quantum complexity cl…