Односторонняя квантовая проверка

Теория вычислений состояния кластера к настоящему времени хорошо известна, показывая, что любая схема BQP может быть модифицирована таким образом, чтобы она использовала только однобитовые квантовые вентили, возможно, с классическим управлением, при условии достаточного запаса состояния, известного как «состояние кластера», которое простейший стабилизатор состояния.

У меня вопрос: известно ли подобное понятие для квантовой проверки - то есть можно ли заменить схемы QMA классически управляемыми затворами в 1 кубит, возможно, используя какое-то «особое состояние»? По крайней мере, на начальном этапе мне неясно, почему состояние кластера может даже работать в этом случае.

quantum-computing Лиор Эльдар
источник

Если я правильно понимаю, проблема в том, что в QMA Merlin вручает вам квантовое доказательство того, что вы должны каким-то образом включиться в модель? Другими словами, если бы это был QCMA вместо QMA, где Мерлин просто вручил вам классическую строку, то мы могли бы просто использовать известные результаты для BQP, верно?

Робин Котари

Да, это правильно. Спасибо за то, что сделали это различие.

Лиор Эльдар

Начнем с того, что можно задать тот же вопрос для BQP: можем ли мы выполнить какое-либо квантовое вычисление, учитывая мощность для выполнения 1-кубитных измерений и предоставляя ненадежные кластерные состояния (или какое-либо другое подходящее состояние)?

Норберт Шух

Ответы:

Можно ограничить верификатор QMA измерениями одного кубита и классической предварительной и постобработкой (со случайностью), сохраняя при этом QMA-полноту.

Чтобы понять почему, возьмем любой класс локальных QMA-полных гамильтонианов на кубитах. Путем добавления константы порядка и масштабирования с коэффициентом гамильтониан может быть приведен в форму где , , а $k$ $\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$

H = \sum_{i} w_{i} h_{i},

$H=\sum_i w_i h_i\ ,$

w_{i} > 0

$w_i>0$

\sum_{i} w_{i} = 1

$\sum_i w_i=1$

, где

- произведение Паулиса. Оценивая наименьшее собственное значение

до точности

попрежнему QMA-трудно.

h_{i} = \frac{1}{2} (I d \pm P_{i})

$h_i = \tfrac12(\mathrm{Id}\pm P_i)$

P_{i}

$P_i$

H

$H$

1 / p o l y (n)

$1/\mathrm{poly}(n)$

Теперь мы можем построить схему, которая использует только измерения одного кубита, которые, учитывая состояние , принимает с вероятностью (который по построению находится между и ). Для этого сначала случайным образом выберите один из соответствии с распределением . Затем измеряют каждый из Paulis в , и взять на четность из результатов, которые в настоящее время связанные с $|\psi\rangle$ $1-\langle\psi|H|\psi\rangle$ $0$ $1$ $i$ $w_i$ $P_i$ $\pi$ $\langle\psi|h_i|\psi\rangle$ через Теперь схема выводит, а выходной поэтому распределяетсясоответствии с.

⟨ ψ | h_{i} | ψ ⟩ = \frac{1}{2} (1 \pm (- 1)^{π}) \in {0, 1} .

$\langle\psi|h_i|\psi\rangle = \tfrac12(1\pm (-1)^\pi)\in\{0,1\}\ .$

1 - ⟨ ψ | h_{i} | ψ ⟩

$1-\langle\psi|h_i|\psi\rangle$

⟨ ψ | H | ψ ⟩

$\langle\psi|H|\psi\rangle$

Это, если мы выбрали да-экземпляр (QMA-полной) локальной гамильтоновой задачи, существует состояние таким образом, что это верификатор будет принимать с некоторой вероятностью , в то время как в противном случае любое состояние будет отклонена с вероятностью , с . Поэтому вариант QMA , где верификатор ограничивается измерениями одного кубита является QMA-полна для некоторого $|\psi\rangle$ $\ge a$ $\le b$ $a-b>1/\mathrm{poly}(n)$ $1/\mathrm{poly}(n)$ разрыв. Наконец, эту версию QMA можно усилить, используя только обычные методы усиления для QMA, что в конечном итоге доказывает, что оно является QMA-полным независимо от разрыва (в том же диапазоне, что и QMA).

Норберт Шух
источник

H

$H$

H^{'}

$H'$

ϵ = 1 / p o l y (n)

$\epsilon=1/\mathrm{poly}(n)$

H = x (H^{'} + y)

$H=x(H'+y)$

x = 1 / p o l y (n)

$x=1/\mathrm{poly}(n)$ and

y = p o l y (n)

$y=\mathrm{poly}(n)$ , so estimating the G.S. energy of

H

$H$ up to accuracy

x ϵ = 1 / p o l y (n)

$x\epsilon=1/\mathrm{poly}(n)$ is still QMA-hard.

Norbert Schuch

Can you always assume that

h_{i}

$h_i$ is a projector onto an eigenspace of a Pauli Hamiltonian?

Henry Yuen

Well, each term

h^{'}

$h'$ in the original Hamiltonian can be written as a sum of

4^{k}

$4^k$ Pauli products (

4^{k} = p o l y (n)

$4^k=\mathrm{poly}(n)$ for

k = O (\log (n))

$k=O(\log(n))$ ), and the prefactor of each Pauli product

P_{i}

$P_i$ is

t r [P_{i} h^{'}] / 2^{k} \leq ‖ h^{'} ‖_{\infty}

$\mathrm{tr}[P_ih']/2^k\le \|h'\|_\infty$ .

Norbert Schuch

My interpretation of the question is that you are asking, may we assume that the verifier circuit for a QMA protocol uses only single-qubit measurements? (The idea being that the prover sends you both the quantum proof and the quantum cluster state needed to implement the original verification circuit by "one-way quantum computing.")

The problem, of course, is that the prover might not send you a valid cluster state at all. So the verifier would have to test the received state to make sure that it really is a cluster state. The verifier does this by making single-qubit measurements and checking the correlations satisfy the necessary stabilizer checks. Since such testing is destructive to the state, there would need to be a procedure where the verifier is given many copies of the state, checks most of them, and uses a random one for the computation. Do polynomially many copies suffice?

I don't think this is a known theorem. I don't see an obvious counterexample (with a minute's thought), so it might be believable. Known proof technology on testing states seems like it should be enough to check this. For example, see Matthew McKague's paper arXiv:1010.1989 [quant-ph]. If you get a proof working, send the paper to QIP (deadline Oct. 5)!

Anonymous
источник

Perhaps I am misunderstanding this question. If you are asking whether you can implement the verifier circuit for a problem in QMA using a measurement based computation, where Merlin supplies the input layer, and Arthur supplies all further qubits in the resource state and entangles both sets of qubits before measurements commence, then the answer is trivially yes. This follows directly from the fact that any quantum circuit can be implemented as a measurement based computation whether you care about classical or quantum input.

You'll notice that in most papers on measurement based computation input sites are generally identified separately from the other sites, and this is why (i.e. specifically to deal with the case of quantum input).

Joe Fitzsimons
источник

Actually I'm unclear on this point. In the papers of measurement-based computation I've looked at, the transformation is from any BQP circuit with classical input, to a one-way computation circuit starting from the cluster state. That is, to say, it is NOT described as a transformation taking any arbitrary unitary circuit U to a measurement-based circuit U_1, regardless of the input. While the complexity question I had asked, is now resolved following Norbert's answer, I would still like to understand this point.

Lior Eldar

@LiorEldar: Then you should look at the original Raussendorf and Briegel paper or the Raussendorf, Browne and Briegel one. They explicitly construct circuits one gate at a time, showing that each measurement pattern implements a given gate on the input layer, which can be in an arbitrary state. You most definitely can implement arbitrary circuits on arbitrary inputs.

Joe Fitzsimons

Lior was actually around here in Aachen when we discussed this, and one way to understand the question is based on this idea: Could Merlin provide the proof built into an (untrusted) cluster state, and Arthur uses his one-qubit measurements to either verify the cluster or verify the proof using MBQC? (Maybe one could use similar ideas as in blind comp. where error correction is used?) Unfortunately, one doesn't need this nice idea to prove QMA-hardness. ;-( However, I believe it is still an interesting question to understand if this would work, and you would be the expert to show this :-)

Norbert Schuch

@Lior: If you want to use MBQC to verify the input, you of course also need to 2-qubit gates in addition to the one-qubit measurements (since you need to entangle the input with your cluster state).

Norbert Schuch

@Joe: BTW, the same question for BQP (can we run BQP using 1-qubit measurements using an untrusted cluster state) is of course still open, and it feels to me that the ideas used in blind computation might be the way to go.

Norbert Schuch