Quantum measurement occurrence is undecidable

A. M. Turing Proc. London Math. Soc. (1937) s2-42(1): 230-265

1937

Earlier work this paper cites.

E. Post, Bull. Amer. Math. Soc. 52

1946

Earlier work this paper cites.

S. C. Kleene, Mathematical logic

1967

Earlier work this paper cites.

M. S. Paterson, Stud. Appl. Math. 49

1970

Earlier work this paper cites.

G. H. Hardy and E. M. Wright, An introduction to the theory of numbers

1980

Earlier work this paper cites.

M. A. Miller, Mathematics Magazine 67

1994

Earlier work this paper cites.

V. D. Blondel and J. N. Tsitsiklis, Inf. Process. Lett. 63

1997

Cited alongside, same era.

V. Halava and T. Harju, Amer. Math. Monthly 108

2001

Cited alongside, same era.

V. D. Blondel, E. Jeandel, P. Koiran, and N. Portier, SIAM J. Comput. 34

2005

Cited alongside, same era.

J. Kempe, A. Kitaev, and O. Regev, SIAM Journal of Computing 35

2006

Cited alongside, same era.

V. Halava, T. Harju, and M. Hirvensalo, Int. J. Found. Comp. Sc. 18

2007

Cited alongside, same era.

D. Perez-Garcia, F. Verstraete, M. M. Wolf, and J. I. Cirac, Quantum Inf. Comput. 7

2007

Cited alongside, same era.

T. J. Osborne, arXiv:1106.5875

Original

Cited in the paper.

T. S. Cubitt, J. Eisert, and M. M. Wolf, arXiv:0908.2128

Original

Cited in the paper.

In unpublished work it has been shown that to decide whether a local Hamiltonian is frustration-free or not is undecidable [ 8 ]

Cited in the paper.

Ref. [ 11 ] relates the problem whether the language recognized by a quantum finite automaton is empty or nonempty to the PCP

Cited in the paper.

In the unpublished Ref. [ 8 ] , it is shown that the question whether a given many-body model is frustration-free is undecidable

Cited in the paper.

Note that for a matrix-product state vector | ψ ⟩ |\psi\rangle of the above kind, ⟨ j 1 , … , j n | ψ ⟩ = ⟨ R | A j n … A j 1 | L ⟩ \langle j_{1},\dots,j_{n}|\psi\rangle=\langle R|A_{j_{n}}\dots A_{j_{1}}|L\rangle

Cited in the paper.

S. Bravyi and B. Terhal, SIAM J. Comput. 39

2009

Later among the works it cites.

D. Aharonov, D. Gottesman, S. Irani, and J. Kempe, Comm. Math. Phys. 287

2009

Later among the works it cites.

J. Eisert, M. Cramer, and M. B. Plenio, Rev. Mod. Phys. 82

2010

Later among the works it cites.

M. Sanz, D. Perez-Garcia, M. M. Wolf, and J. I. Cirac, IEEE Trans. Inf. Theory 56

2010

Later among the works it cites.

D. Gross, J. Eisert, N. Schuch, and D. Perez-Garcia, Phys. Rev. A 76

2010

Later among the works it cites.

“Frustratingly undecidable (or undecidably frustrating)”, talk held by T. S. Cubitt at IQC Waterloo, (03. Aug. 2011)

2011

Closest in time.