Individual quantum measurements can be viewed as questions posed by an observer and answered by nature. More complex phenomena emerge with the shift from observers to active agents that adjust future actions based on measurement outcomes [1]. One interesting example is the undoing of measurements in case of undesired outcomes [2]–[6]. This potentially provides a powerful tool to the agent. In this paper we demonstrate that in certain instances it is indeed too powerful to be compatible with the existence of computationally hard problems. We construct a formally valid POVM that would allow an efficient solution to the 3SAT problem. Thus, we propose that performing this measurement must itself be prohibitively complex, and thus it is not realized in nature. Thus, while quantum computing is a key area where our results apply, our argument is independent of task-specific quantifiers of complexity such as circuit complexity, and also applies to (yet unknown) “native gates” as provided by nature. For sufficiently large problem instances, such measurements are thus unreachable for any observer with finite resources. Hence, we term the associated quantities unobservables. In particular, we show that there exist states such that their superposition is operationally indistinguishable from a mixture. Thus, a main consequence of unobservables is decoherence in the sense that coherence of certain states cannot be observed. This opens up the possibility that complexity, rather than environmental interactions as in the more common approach [7], [8], may be a source of decoherence.

Prior work by Aaronson et al. has demonstrated a link between the complexity of measuring superpositions and that of unitary time evolution of states [9]. Here, we link the observability of coherence directly to a computationally hard problem for the first time.

Quantum measurement is usually cast in terms of irreversibility. However, for present purposes, it is important to note that sometimes quantum measurements can indeed be undone. One approach towards the quantum measurement problem(s) [10], [11] is considering a global unitary time evolution that entangles system and environment. With full control over the environment we could in principle undo the measurement. Similar reasoning applies to ‘Wigner’s Friend’-type scenarios [2], [6]. Other schemes for ‘undoing’ measurements are based on weak measurements [3], [4]. Measurements can also be treated as errors that are corrected using quantum error correction codes [5]. The smallest possible example is the four-qubit CSS code [12], [13] which encodes two logical qubits into four physical ones. It can correct a single measurement ‘error’ at a known position, see Appendix 1.

We proceed to sketch an algorithm that attempts to exploit the undoing of measurements by performing a follow-up measurement to ‘reset’ unwanted outcomes (see Appendix 2 for details). The algorithm is designed to determine the satisfiability of a propositional logic formula \(F\) in CNF. \(F\) contains \(N\) variables \(v_1\), \(v_2\), …, \(v_N\) which appear in \(M\) clauses \(C_m\) of exactly three different literals each. We denote literals \(l_{mj} = \sigma_{mj} v_{q_{mj}}\), where \(\sigma_{mj}=\pm 1\) and \(q_{mj}\in\{1,2,\dots,N\}\) (a negative literal \(-v_i\) corresponds to \(\lnot v_i\)). Then \[F = \bigwedge_{m=1}^M \bigvee_{j=1}^3 l_{mj}.\] We associate a qubit with each of the \(N\) variables, such that \(\ket{0}_i\) and \(\ket{1}_i\) correspond to the values false and true of the variable \(v_i\), respectively. We say that a state fulfills a clause, if the state has no component violating it.

The algorithm is based on the following quantum measurements. In a slight abuse of notation we use the same symbols for the general case and the specific formula \(F\) defined above. Let \(\Pi(C_m)\) and \(\Pi(\lnot C_m)\) project onto the subspace of states fulfilling and violating clause \(C_m\), respectively. The corresponding projective measurement is \[\mathcal{M}(C_m) = \{\Pi(C_m),\; \Pi(\lnot C_m)\}. \label{eq:defmeasurement}\tag{1}\] A possible implementation of \(\mathcal{M}(C_m)\) is shown in 1. Analogously we define \(\mathcal{M}\) also for XOR-clauses with a possible implementation shown in [fig:measurementforxorclause]. Finally, we define for a formula \(F=\bigwedge_{i=1}^M C_i\) the sandwich-POVM \[\mathcal{N}(F) =\{P_x(F) Q_y P_x(F)| 0\leq x < 2^M, 0\leq y< 2^N\},\] where \[P_x(F) = \prod_{i=1}^M\Pi((-1)^{x_i} C_i)\] can be considered a sequential measurement of the \(\mathcal{M}(c_i)\) and \[Q_y = \bigotimes_{i=1}^N \frac{\mathbb{1}+(-1)^{y_i} X}{2}\] is a measurement in the \(X\)-basis with outcomes \(x=x_1,x_2,...,x_t\) and \(y\), respectively. The post-measurement state of the sandwich-POVM is obtained via the quantum channel with Kraus operators \[\begin{align} M_{x,y} =&\sqrt{ P_x(F) Q_y P_x(F) } \\ =& \sqrt{\frac{2^N}{\mathop{\mathrm{tr}}P_x(F)}} P_x(F) Q_y P_x(F). \end{align}\] The last equation holds, because \(P_x(F) Q_y P_x(F)\) is rank one. \(\mathcal{N}\) undoes measurements of \(\mathcal{M}\) on \(P_x(F)\ket{+}^{\otimes N}\) up to irrelevant phases. The right \(P_x(F)\) fixes the outcome \(x\), the \(Q_y\) erases any unwanted projection introduced by \(\mathcal{M}\), before the left \(P_x(F)\) projects back to the support of \(P_x(F)\).

Even though \(P_x(F)\) and \(Q_y\) are easy to implement, \(\mathcal{N}\) may not be experimentally realizable for sufficiently large \(N\), e.g. for hundreds of variables [14]. In fact we will lead the following two main assumptions to a contradiction:

Assumption (INC)

NP \(\not\subseteq\) BQP [15], i.e. quantum systems do not allow to efficiently solve NP-hard problems.

Assumption (OBS)

Every formally valid measurement can be experimentally realized, including \(\mathcal{N}(F)\), for a formula \(F\) such that its satisfiability problem is too hard to solve (with the finite resources available to any observer).

We exploit assumption (OBS) and the described undoing of the measurement \(\mathcal{M}\) in the following algorithm to find a solution of \(F\). We want to transform \(\ket{+}^{\otimes N}\) into a solution of \(F\) by sequentially measuring whether the state satisfies clause \(C_m\), always undoing the unwanted answer ‘no’. See 2 for an overview of the main idea. However, there is a technical difficulty that requires some additional effort: The success probability of any of these steps might be prohibitively low at any \(m\), see Appendix 3. To circumvent this, we “dilute” clauses to weaken their effect on the solution space, increasing the success probability for measuring the \(\Pi(C_i)\) outcome. By this we mean that we replace the formula \(F\) by a ‘diluted’ formula \(\mathcal{D}(F)\) with \(M'=6M\) clauses on \(N'=N+M\) variables. The \(M\) new variables \(v_{N+i}\) with \(i=1,2,\dots,M\) encode whether the corresponding clauses \(C_{i}\) are satisfied, i.e. \(C_{i}\leftrightarrow v_{N+i}\). The conversion into CNF yields the first \(4 M\) clauses. The main trick, inspired by XORSample [16], is to then add \(M\) random XOR clauses, that only check the parity of the number of satisfied clauses. This roughly removes half of the non-solution assignments per random XOR clause. Finally we add \(M\) clauses to ensure that all new variables are true, such that \(\mathcal{D}(F)\) is equivalent to \(F\). We give an explicit construction and prove the following properties in Appendix 4:

1. \(\mathcal{D}(F)\) is satisfiable if and only if \(F\) is satisfiable. In this case, the solutions of \(F\) and \(\mathcal{D}(F)\) are identical on the first \(N\) variables.

2. If \(F\) is satisfiable, then the probability to measure \(\Pi(C_i')\) for each \(C_i'\in\mathcal{D}(F)\) is greater than \(\frac{1}{2}\) on average.

The steps of this hypothetical quantum algorithm are shown in 3. A detailed example is given in Appendix 5. We remark that the algorithm cannot be simulated efficiently, e.g. the required size of a classical memory to store the quantum state scales exponentially in the number of variables.

3 would solve an NP-hard problem in polynomial time. There are good reasons to believe this to be physically impossible; indeed, Aaronson has proposed that the impossibility to implement such a process might become a restriction on physical possibility with a similar status as the second law of thermodynamics, and prove a useful guide in the search for new theories [15]. Thus, we propose that this implies that assumption (OBS) fails to hold. The implication is severe: There is a problem size for which the measurement of \(\mathcal{N}(F)\) cannot be carried out with the finite resources of any observer. Thus, for this problem size, \(\mathcal{N}(F)\) is a simple example of a POVM that has no counter-part in any physical system, even for comparatively modest system sizes. Consequently, there are mathematically valid quantum measurements that are not physically realizable. Hence, the associated quantities are unobservables in the above sense. While one might arrive at this conclusion via different routes, for present purposes any unobservable is related to a computationally hard problem that scales superpolynomially in the input size and the given input size is large enough such that any observer does not have enough resources to measure it. Note that this conclusion is independent of the concrete physical realization of any experiment.

We only considered ideal operations, i.e. we did not prove that measurements arbitrarily close to \(\mathcal{N}\) are also unobservable. However, any measurement that is close to \(\mathcal{N}\) will still allow to solve the same 3SAT problem, so the same reasoning applies to approximations of \(\mathcal{N}\) as well. We sketch this reasoning in Appendix 6, by proving that any realization of a quantum algorithm that is \(\frac{\epsilon}{L}\)-close in diamond norm to the ideal implementation, where \(L\) is the number of operations, gives outcome probabilities that are \(\epsilon\)-close to the ideal one.

In the remainder we give a simple example and look at interesting consequences of unobservables: Unitaries that do not correspond to physical time evolutions and macroscopic but finite states whose coherence is unobservable.

We established that the sandwich-POVM \(\mathcal{N}(f)\) is unobservable. This unobservable POVM is linked to unobservable PVMs via Naimark’s dilation theorem. The isometry [17] \[V = \sum_{x=0}^{2^N-1}\sum_{y=0}^{2^M-1} \ket{x, y} \bra{y}H^{\otimes N} P_x(F),\] fulfills \[V^\dagger\proj{x,y} V = P_x(F) Q_y P_x(F).\] One can extend \(V\) to a unitary \(U\), such that the POVM is equivalent to applying \(U\) followed by a canonical basis measurement. We define the corresponding Hermitian operator \[\tilde{Z} = U^\dagger Z U \label{eq:Ztilde}\tag{2}\] where \[Z = \sum_{z=0}^{2^{M N}-1} \omega^z \proj{z} \text{ with } \omega = \mathrm{e}^{2\pi \mathrm{i}\cdot 2^{-(M+N)}}\] is the usual \(2^{M+N}\)-dimensional Pauli-\(Z\) operator. Note that \(Z\) is observable but \(\tilde{Z}\) is an unobservable. Likewise, the operators \[\tilde{X}:=H \tilde{Z} H^\dagger, \text{ and }\tilde{Y}:=\mathrm{i} H \tilde{Z},\] where \(H\) is the Fourier transformation, are unobservables. Analogously to 2 we can define \(\tilde{X}\) and \(\tilde{Y}\). Then \(\tilde{X}\), \(\tilde{Y}\), and \(\tilde{Z}\) are Pauli operators on a \(2^{M+N}\)-dimensional qudit. Therefore, there is a qudit space on which all Pauli-operators are unobservables. Note however, that the canonical qudit shares the same state space and the corresponding Pauli operators are observable.

The unitary \(U\) in 2 maps the unobservable \(\tilde{Z}\) to the observable \(Z\). Thus \(U\), as any unitary that transforms an unobservable into an observable, cannot be realized as a physical time evolution. This recapitulates the result of [9], without relying on a specific quantifier of complexity, such as the quantum circuit complexity employed there. Let \(\mathcal{T}\) be the set of physically realized time evolutions using only the finite resources (time, energy, space) available to the observer. \(\mathcal{T}\) does not contain all unitary operators, as illustrated by \(U\). This motivates us to define the time-evolution orbit of a mixed or pure state as \[\begin{align} \mathcal{T}(H):=&\{U H U^\dagger \;|\; U\in \mathcal{T}\} \\ \text{ and } \mathcal{T}(\ket{\psi}) =& \{U \ket{\psi} \;|\; U\in \mathcal{T}\}, \end{align}\] respectively.

We associate states \[\begin{align} &\rho = \sum_{z=0}^{2^{M+N}-1} p_z \proj{z} \text{ and } \tilde{\rho} = U \rho U^\dagger\\ \text{with }&\sum_{z=0}^{2^{M+N}-1} p_z = 1 \text{ and } p_i\neq p_j \;\forall i \neq j, \end{align}\] with the observable \(Z\) and the unobservable \(\tilde{Z}\), respectively. Any unitary \(U'\) with \(U'\rho U'^\dagger = \tilde{\rho}\) maps the observable \(Z\) onto the unobservable \(\tilde{Z}\) and is therefore not a physically realizable time evolution. Indeed such \(U'\) is equal to \(U\) up to a unitary which is diagonal in the computational basis.

The complexity to evolve \(\rho\) into \(\tilde{\rho}\) is smaller or equal to the minimum complexity to evolve any purification of \(\rho\) into any purification of \(\tilde{\rho}\), as the latter accomplishes the former as well. This implies that there are also two pure states \(\ket{\psi_1}\) and \(\ket{\psi_2}\) which are not connected by any unitary time evolution in \(\mathcal{T}\), i.e. \(\ket{\psi_2}\not\in \mathcal{T}(\ket{\psi_1})\). By definition of \(\mathcal{T}\), there is no time-efficient way to map \(\ket{\psi_1}\) to \(\ket{\psi_2}\), i.e. any unitary time evolution \(W(t)\) with \(W(t)\ket{\psi_1} = \ket{\psi_2}\) requires exponential time \(t=\exp(\Omega(N))\). Again we think of an \(N\) which is large enough such that \(t\) is prohibitively large for the finite resources of any observer. The slow evolution implies a weak coupling and the transition probability \(|\bra{\psi_2}W(t_0)\ket{\psi_1}|^2=\exp(-\Omega(N))\) is small for sub-exponential time \(t_0\). Hence, any unitary \(V\) in \(\mathcal{T}\) fulfills \[\left|\bra{\psi_1} V \ket{\psi_2}\right| = \exp(-\Omega(N)).\quad \forall V\in\mathcal{T} \label{eq:unitaryinT}\tag{3}\] Now, employing the von Neumann model, any measurement is implemented as a unitary interaction on the system and the measurement apparatus followed by a measurement of the state of the apparatus [18]. For a unitary measurement operator \(A=\sum_{i=1}^d \lambda_i A_i\) which associates labels \(\lambda_i\in\mathbb{C}\) to \(d\) projectors \(A_i\), the corresponding interaction can be written as \[C_A = \sum_{i=1}^d \proj{i} \otimes \lambda_i A_i\] and the measurement apparatus is initialised in the \(\ket{+}:=\frac{1}{\sqrt{d}}\sum_i \ket{i}\) state and finally measured in the Fourier basis. The case of non-unitary measurement operators is handled by relabeling the measurement outcomes. Note that \(A\) is not necessarily Hermitian, but it is a normal operator and the spectral theorem holds by construction. For an observable \(A\) we calculate \[\begin{align} \left|\bra{\psi_1} A \ket{\psi_2}\right| \overset{\hphantom{\text{\ref{eq:unitaryinT}}}}{=}& d^2 \left|\bra{+}\bra{\psi_1} C_A \ket{+}\ket{\psi_2}\right|\\ \overset{\text{\ref{eq:unitaryinT}}}{=}& \exp(-\Omega(N)). \label{eq:unitaryofmeasurement} \end{align}\tag{4}\] We remark that for \(A=\mathbb{1}\) this implies that the two states \(\ket{\psi_1}\) and \(\ket{\psi_2}\) are practically orthogonal. 4 implies that the expectation values of \(A\) in the states \[\begin{align} \rho_{\mathrm{coh}} =& \frac{1}{2}(\ket{\psi_1}+\ket{\psi_2})(\bra{\psi_1}+\bra{\psi_2})\\ \text{and }\rho_{\mathrm{incoh}} =& \frac{1}{2}(\ket{\psi_1}\bra{\psi_2}+\ket{\psi_2}\bra{\psi_2}), \end{align}\] are indistinguishable, as \[\begin{align} &\mathop{\mathrm{tr}}(A \rho_{\mathrm{coh}})-\mathop{\mathrm{tr}}(A \rho_{\mathrm{incoh}})\\ =&2\mathrm{Re}(\bra{\psi_1}A\ket{\psi_2}) \overset{\ref{eq:unitaryofmeasurement}}{=} \exp(-\Omega(n)). \end{align}\] The coherent superposition of two states which are not connected by time-evolution cannot be distinguished from the incoherent mixture of the two.

The coherence of the state \(\rho_{\mathrm{coh}}\) cannot be observed and in this sense we arrived at the concept of decoherence. This vanishing of interference between different (sets of) states is a hallmark of the presence of a SSR. SSRs were introduced in 1952 by Wick, Wightman, and Wigner [19] to account for the fact that certain quantities, like charge or spin, seem exempt from the superposition principle. The inability to detect interference between the states \(\ket{\psi_1}\) and \(\ket{\psi_2}\) entails that any admissible observable \(O\) must be diagonal in the basis spanned by these states.

Two relevant consequences of the existence of an SSR are, first, that a formally pure superposition corresponds to a mixture, as shown above, and second, that this decomposition is unique. This stands in contrast to ordinary mixed states, which do not have a unique extremal decomposition in general. In particular, this suggests that it is permissible to apply an ignorance interpretation to such a mixture, interpreting the coefficients of its convex decomposition as probabilities of finding the system in a given state. On this basis, SSRs have been proposed to deliver a ‘wash-out’ solution to the measurement problem, where interference vanishes to leave only classical probabilities (e.g. see [20]–[25]).

It remains to be seen whether the ‘effective’ SSR introduced here can fulfill this role. Of note, this is not the first time that limitations of the observer have been appealed to with regard to SSRs: Landsman, e.g., appeals to the localized nature of the observer to justify the impossibility of detecting interference between sufficiently separated states [24], while the program of einselection (environmentally induced superselection) seeks to similarly define effective or FAPP superselection rules based on environmental decoherence effects [26]. Along a different route, Peres has argued that the complexity of performing certain measurements is the reason for the appearance of irreversibility [27]. However, to the best of our knowledge, this is the first time that computational complexity has been investigated as a source of superselection.

Let us summarize the chain of arguments that have brought us here. We started out by showing that the existence of computationally hard problems implies that there are measurements which cannot be performed. More concretely, we showed that the sandwich-POVM \(\mathcal{N}\) would allow us to efficiently solve 3SAT problems. Thus, while these are perfectly valid measurements in the standard formalism of quantum mechanics, they cannot correspond to observables: rather, they represent unobservables. For example, sufficiently large Hilbert spaces contain qudits where Pauli matrices correspond to unobservables. Next we discussed the following consequences. There are unitary operators which are not physically realized as time evolutions in any system. And there are even states which are not connected by any physical time evolution, leading to the concept of time-evolution orbitals. Finally, we saw that no coherence can be observed between two states if one cannot time-evolve one into the other. As discussed above this implies that we can switch from a quantum description of the state of a system to classical probabilities and in this sense classicality emerges. In this paper we only showed the existence of this mechanism. We do not expect this mechanism to be the only reason for a classical world, and a future quantitative analysis of unobservables may estimate how large its contribution is: Are many quantum phenomena not visible in macroscopic systems, because observing them is too hard in a complexity theoretic sense?

1 Undoing a Measurement with a Four-Qubit Code↩︎

In the following we describe a code that can undo a measurement with the smallest number of qubits possible. The code \(q_4\) is a CSS code [12], [13] that encodes two logical qubits into four physical ones, with a code distance of two. Hence, in the usual notation, it is a [[4,2,2]] code. This code can detect a single-qubit error. If the position of the error is known, then it allows to correct it. Hence it can correct a single erasure. The stabilizer is generated by the operators \[\begin{align} g_1 =& X_1 X_2 X_3 X_4\\ g_2 =& Z_1 Z_2 Z_3 Z_4 \end{align}\] and we choose the logical operators \[\begin{align} \overline{X}_1 =& X_2 X_3,\\ \overline{X}_2 =& X_2 X_4,\\ \overline{Z}_1 =& Z_2 Z_4,\\ \text{and } \overline{Z}_2 =& Z_2 Z_3. \end{align}\] The logical basis states are \[\begin{align} \ket{\overline{00}} =& \frac{1}{\sqrt{2}}\left(\ket{0000}+\ket{1111}\right),\\ \ket{\overline{10}} =& \frac{1}{\sqrt{2}}\left(\ket{0110}+\ket{1001}\right),\\ \ket{\overline{01}} =& \frac{1}{\sqrt{2}}\left(\ket{0101}+\ket{1010}\right),\\ \text{and }\ket{\overline{11}} =& \frac{1}{\sqrt{2}}\left(\ket{0011}+\ket{1100}\right). \end{align}\] Performing a measurement on the first qubit (and ignoring the outcome) is equivalent to replacing it by a completely mixed state. Mathematically, for any code word \(\ket{\overline{\psi}}\) \[\frac{\mathbb{1}}{2} \otimes \mathop{\mathrm{tr}}_1 \proj{\overline{\psi}} = \frac{1}{4}\sum_{e\in \{\mathbb{1},X_1,Y_1,Z_1\}} e\proj{\overline{\psi}}e^\dagger,\] which we interpret as a single qubit error \(\mathbb{1}\), \(X\), \(Y\), or \(Z\) occurring with probability \(\frac{1}{4}\) each. This error can be corrected by performing a syndrome measurement, and correcting it by applying an operation that anti-commutes with the corresponding stabilizer generators, see 1.

Let us take a closer look at how this works. Assume we started out in the state \[\ket{\overline{\psi}} = \alpha \ket{\overline{00}} + \beta \ket{\overline{10}} + \gamma \ket{\overline{01}} + \delta \ket{\overline{11}}\] and measured \(\ket{0}\) on the first qubit. The state collapsed into \[\begin{align} \ket{\psi'} =& \proj{0}_1 \ket{\overline{\psi}}\\ \propto& \ket{0} \left(\alpha \ket{000} + \beta\ket{110}+\gamma \ket{101} + \delta\ket{011}\right). \end{align}\] We now do a syndrome measurement, where the outcome of \(g_2\) is always \(+1\), however, the outcome of \(g_1\) is random. We consider both cases:

1. The syndrome is \(00\), so we apply no correction. The state is \(\frac{1}{2}(\mathbb{1}+g_1) \ket{\psi'} \propto \ket{\overline{\psi}}\).

2. The syndrome is \(10\), so we apply \(Z_1\) and the state is \(Z_1 \frac{1}{2}(\mathbb{1}-g_1) \ket{\psi'} \propto \ket{\overline{\psi}}\).

Either way, we restored the original state that described the system prior to the collapse. A similar analysis can be done for other measurement bases. It is noteworthy that the entanglement is restored by the measurement, not by the correction, which only affects a single qubit.

As the measurement is reversible, the “collapse” does not erase any information. It can therefore also be achieved with a unitary operation, which is another way of seeing that it can be undone, see 4.

The reversible measurement could also be replaced by a measurement with post-selection. However, the success probability then scales differently with the number of measurements.

2 Detailed description of the algorithm↩︎

Consider a propositional logic formula in CNF with \(N\) variables \(v_1\), \(v_2\), …, \(v_N\) and \(M\) clauses of exactly three different literals each. We denote positive literals with \(+v_i\) and negative literals (i.e. \(\lnot v_i\)) with \(-v_i\). The formula can be expressed as \[\begin{align} {2} F =& \bigwedge_{m=1}^M C_m,\\ \text{with clauses } C_m =& \bigvee_{j=1}^3 l_{mj}\quad m=1,2,...,M \end{align}\] and literals \(l_{mj} = \sigma_{mj} v_{q_{mj}}\), where \(\sigma_{mj}=\pm 1\) and \(q_{mj}\in\{1,2,\dots,N\}\). The task is to determine whether there is an assignment of truth values to the variables \(v_1\), \(v_2\), ..., \(v_N\), such that \(F\) evaluates to true. If such an assignment exists, we call \(F\) satisfiable. The algorithm described below actually also returns an assignment of truth values to the variables if \(F\) is satisfiable, but we will not need it.

We associate a qubit with each of the \(N\) variables, such that \(\ket{0}_i\) and \(\ket{1}_i\) on qubit \(i\) correspond to the values false and true of the variable \(v_i\), respectively. We denote the corresponding state space \(\mathcal{H}_{2^N}\).

In the following we will define different mathematically valid measurements related to the given formula \(F\) as defined above.

First we associate a projector \(\Pi(F)\) with an arbitrary propositional logic formula \(F\) on (a subset of) the \(N\) variables such that it projects onto the space of fulfilling assignments of \(F\). We can write \[\Pi(F) = \sum_{\substack{v_1,v_2,...,v_n=0\\F(v_1,v_2,...,v_N)=\relax\ifmmode\mathrm{true}\else\textit{true}\fi}}^1 \proj{v_1}\otimes \proj{v_2}\otimes ... \otimes \proj{v_N}.\] The following special cases will be useful in constructing the algorithm. The projectors \[\begin{align} \Pi(C_m) =& \mathbb{1}- \Pi(\lnot C_m)\\ \text{and }\Pi(\lnot {C}_{m}) =& \prod_{j=1}^3 \Pi(\lnot l_{mj}) \end{align}\] with \[\Pi(\lnot l_{mj}) = \frac{\mathbb{1} + \sigma_{mj} Z_{q_{m,j}}}{2}\] project onto the subspace of states fulfilling and violating the \(m\)-th clause in \(F\), respectively. We denote the dichotomic PVM formed by these projectors by \[\mathcal{M}(C_m) = \{\Pi(C_m),\; \Pi(\lnot C_m)\}. \label{eq:defmeasurementappendix}\tag{5}\] So \(\mathcal{M}(C_m)\) answers the question whether the state of the \(N\) qubits fulfills or violates the \(m\)-th clause of \(F\). As \(\Pi(C_m)\) only involves three qubits, the measurement \(\mathcal{M}(C_m)\) is easy to implement independently of \(N\) and \(M\), see 1.

If we would measure the ‘yes’-outcome for all clauses, we would know for sure that the formula \(F\) would be satisfiable. However, to tackle the undesired ‘no’-outcome, we introduce further measurements.

First we introduce a measurement that will be used below to ensure that the probabability of the ‘no’ outcome will be not larger than \(\frac{1}{2}\). It is defined analogously to \(\mathcal{M}(C_m)\) in 5 as \[\mathcal{M}\left(\mathop{\mathrm{\underline{\bigvee}}}_{i\in S} v_i\right) \label{eq:xormeasurement}\tag{6}\] for some \(S\subset \{1,2,..,N\}\), except that we use the XOR in contrast to the “normal or” that appears in the clauses of \(F\). Also this measurement can be implemented efficiently, see [fig:measurementforxorclause] for an example.

The sequential measurement of \(\mathcal{M}\) for all clauses in \(F\) with outcomes \(x=(x_1, x_2, ..., x_m)\) implements the projection \[P_x(F) = \prod_{i} \left\{\begin{array}{cc} \Pi(C_i) & \text{ if x_i=0}\\ \Pi(\lnot C_i) & \text{ else.} \end{array}\right.\] We can also interpret \(x_i\) as the \(i\)-th digit of an \(m\)-digit binary number \(x=0,1,2,...,2^m-1\). Note that also this measurement can be implemented efficiently. The last measurement we need is a simple measurement in the \(X\)-basis on every qubit with projectors \[Q_y = \bigotimes_{i=1}^N \frac{\mathbb{1}+(-1)^{y_i} X}{2},\] where \(y_i\) is the outcome on qubit \(i\). Again we can interpret \(y_i\) as the \(i\)-th digit of \(y=0,1,2,...,2^N-1\) Note that \(P_x(F)\) and \(Q_y\) do not commute.

Now we gathered everything to finally define the ‘sandwich’-measurement for a (CNF-XOR) formula \(F=\bigwedge_{i=1}^M C_i\), \[\mathcal{N}(F) = \{P_x(F) Q_y P_x(F)| 0\leq x \leq 2^M-1, 0\leq y\leq 2^N-1\}, \label{eq:sandwichmeasurementappendix}\tag{7}\] where we label the outcomes with a multi-index to match the above definitions. We verify that \(\mathcal{N}(f)\) is a POVM, hence a mathematically valid quantum measurement. As the \(P_x(f)\) and the \(Q_y\) are projectors, the elements of \(\mathcal{N}(f)\) are positive semidefinite. Also the completeness condition \[\sum_{x,y} P_x(F) Q_y P_x(F) = \sum_x P_x(F) = \mathbb{1}\] holds. Even if \(P_x(F)\) and \(Q_y\) are easy to implement, and despite the compact form of 7 , \(\mathcal{N}\) may not be implementable for large \(N\). From the point of view of quantum computing this would not be surprising, it requires exponentially (in \(N\)) many gates to implement general operations on \(N\) qubits in a quantum circuit. But what if it so happens that \(\mathcal{N}\) is realized natively in some quantum system? We therefore seek a stronger argument than circuit complexity itself. Indeed we will lead the following main assumption to a contradiction with the natural expectation that NP-hard problems should not be ‘easily’ solvable:

Assumption (OBS)

\(\mathcal{N}(F)\) is an observable for a formula \(F\) whose satisfiability problem is too hard to solve (with the finite resources available to any observer).

If for now we assume that (OBS) holds, then we can use \(\mathcal{N}\) to undo measurements of \(\mathcal{M}\) in the following sense. Let \[\zeta(F)=\{v | F(v_1,v_2,...,v_N)=\relax\ifmmode\mathrm{true}\else\textit{true}\fi\}\] denote the set of solutions of the propositional formula \(F\) and \[\chi(F) := |\zeta(F)|\] denote the number of solutions. Now let \(e\) and \(F= e \land c\) be propositional formulas, which implies \(\zeta(F)\subset\zeta(e)\) and \[\Pi(F)\Pi(e) = \Pi(f).\] Furthermore we define the superposition of those satisfying assignments as \[\ket{\zeta(F)} = \sum_{v\in\zeta(F)} \ket{v_1,v_2,...,v_N}.\] Consider the scenario where we first measured \(\mathcal{M}(e)\) on \(\ket{+}\) with ‘yes’-outcome and then we measured \(\mathcal{M}(c)\) with ‘no’-outcome, so the state is \[\begin{align} \ket{\psi_f} =& \Pi(\lnot c)\Pi(e) \ket{+}\\ \propto& \Pi(\lnot c) \ket{\zeta(e)}\\ \propto& \ket{\zeta(e \land \lnot c)}. \end{align}\] The measurement \(\mathcal{N}(e)\) undoes the effect of \(\Pi(\lnot c)\). In this context, the right \(P_x(e)\) fixes the outcome \(x=0\), \(Q_y\) redistributes the probability amplitudes, while the left \(P_x(e)\) projects back to the space of solutions of \(e\). The post-measurement state is \[\begin{align} {2} &P_0(e) Q_0 P_0(e) \Pi(\lnot c) \ket{\zeta(e)}\\ =&P_0(e) Q_0 \Pi(\lnot c) P_0(e) \ket{\zeta(e)}\\ =&P_0(e) Q_0 \Pi(\lnot c)\ket{\zeta(e)}\\ \propto&P_0(e) Q_0 \ket{\zeta(e\land \lnot c)}\\ =&P_0(e) \proj{+} \ket{\zeta(e\land \lnot c)}\\ \propto&P_0(e) \ket{+}\\ \propto&\ket{\zeta(e)}. \end{align}\] So indeed the projection corresponding to the unwanted measurement outcome has been removed from the state. Other values of \(y\) lead to irrelevant sign flips in this state. Indeed as the phases are irrelevant in our hypothetical algorithm one could even work with classical mixed states, further indicating that the proposed algorithm is not illustrating a quantum advantage but a weakness in the formalism, at least when applied naively. However, no other values for \(x\) are measured: The probability for the previously obtained \({x'}=(0,0,\dots,0)\) is \(1\), because \[\begin{align} {2} &\sum_y\mathop{\mathrm{tr}}\left( P_{0}(e) Q_y P_{0}(e) \proj{\zeta(e\land\lnot c)}\right)\\ =&\mathop{\mathrm{tr}}\left( P_{0}(e) \left(\sum_y Q_y\right) P_{0}(e) \proj{\zeta(e\land\lnot c)}\right)\\ =&\mathop{\mathrm{tr}}\left( P_{0}(e)^2 \proj{\zeta(e\land\lnot c)}\right)\\ =&\mathop{\mathrm{tr}}\left( P_{0}(e) \proj{\zeta(e\land\lnot c)}\right)\\ =&\mathop{\mathrm{tr}}\left(P_{0}(e) \frac{P_{0}(e\land\lnot c)\proj{+} P_0(e\land\lnot c)}{\mathop{\mathrm{tr}}P_0(e\land\lnot c)\proj{+} P_0(e\land\lnot c)}\right)\\ =&\mathop{\mathrm{tr}}\left(\frac{P_0(e\land\lnot c)\proj{+} P_0(e\land\lnot c)}{\mathop{\mathrm{tr}}P_0(e\land\lnot c)\proj{+} P_0(e\land\lnot c)}\right) = 1. \end{align}\] Thus the already established projections \(\Pi(c_i)\) with \(i<\mu\) can be protected, while \(Q_y\) erases the projection \(\Pi(\lnot c_\mu)\).

We exploit assumption (OBS) and the described undoing of the measurement \(\mathcal{M}\) in the following algorithm to find a solution of \(F\). See also 2 for an overview of the main idea.

However, there is a technical difficulty that requires some additional effort: We cannot guarantee that the success probability of the measurement \(\Pi(C_i)\) for a clause \(C_i\) in the state \(\ket{\zeta(e)}\), \[\mathop{\mathrm{tr}}(\Pi(C_i)\proj{\zeta(e)}) = \frac{\chi(e\land C_i)}{\chi(e)},\] is high enough in the sense that its inverse, the expected number of trials, scales polynomially in \(N\). Indeed it is easy to construct a counter example, see Appendix 3. To circumvent this, we “dilute” clauses to weaken their effect on the solution space, increasing the success probability for measuring the \(\Pi(C_i)\) outcome. By this we mean that we replace the formula \(F\) by a randomly chosen ‘diluted’ formula \(\mathcal{D}(F)\) with \(M'=6M\) clauses on \(N'=N+M\) variables. More details on the dilution are given in Appendix 4.

The distinction between satisfiable and unsatisfiable instances is achieved as follows. For satisfiable formulas \(F\), the success probability of the XOR-clauses increases until it reaches \(1\). In contrast, if \(F\) is not satisfiable, then the success probability decreases to zero. The two scenarios can be distinguished with high probability in polynomial time. We give a detailed example of the algorithm in Appendix 5.

3 Hard Formula for the hypothetical Algorithm without Dilution↩︎

The formula with \(N\) variables and \(N\) clauses \[\bigwedge_{i=2}^N (\lnot v_1 \lor v_i) \land v_1\] illustrates why dilution or a similar technique is crucial. The measurement probabilites are \[p_m = \left\{\begin{array}{cc} \frac{2^m + 1}{2^m + 2} & \text{ if }m<N \\ \frac{1}{2^N + 1} & \text{ if }m=N. \end{array}\right.\] The success probability of the last measurement scales exponentially bad in \(N\). The first \(N-1\) clauses create a large inbalance between \(v_1=\relax\ifmmode\mathrm{true}\else\textit{true}\fi\) and \(v_1=\relax\ifmmode\mathrm{false}\else\textit{false}\fi\) with few and many terms in the superposition, respectively.

The formula can be adapted to have three unique literals per clause, e.g. \[\begin{align} &(v_1\lor v_2\lor \neg v_3) \land (v_1\lor \neg v_2\lor v_3) \land (v_1\lor \neg v_2\lor \neg v_3) \land(\neg v_1\lor v_2\lor \neg v_3)\\ \land&(\neg v_1\lor \neg v_2\lor v_3) \land(\neg v_1\lor \neg v_2\lor \neg v_3) \land \bigwedge_{i=4}^N (\lnot v_1 \lor v_2 \lor v_i) \land (v_1\lor v_2\lor v_3) \end{align}\] without changing the exponential decay in the measurement probability for the last clause.

4 Propositional formula dilution↩︎

In this Appendix we define the dilution \(\mathcal{D}(F)\) of a propositional logical formula \(F\) in CNF, prove two properties and give some interpretation.

Note that for us the order of the clauses in \(F\) and \(\mathcal{D}(F)\) matter, as they indicate the order in which the measurements are carried out. Note that the \(M\) new variables \(v_{N+i}\) with \(i=1,2,\dots,M\) encode whether the corresponding clauses \(C_{i}\) are satisfied, as they are equivalent to \[C_{m}':= (v_{N+m} \leftrightarrow C_m).\] We remark that the crucial trick of the \(M\) random XOR clauses, that only check the parity of the number of clauses satisfied is inspired by XORSample [16]. Every random XOR clause removes half of the assignments that violate the original formula, as we will see in the proof of (D2) below.

We now prove the two lemmata that are referred to in the main text as properties (D1) and (D2) of the dilution.

We remark that the effect of the dilution can also be achieved by using the original clauses directly in the XOR clauses without the additional variables. This allows to keep the number of variables equal to \(N\), at the cost of slightly more complicated measurements (which are still efficiently implementable, though).

5 Example for the hypothetical algorithm↩︎

We illustrate 3 for the example formula with \(M=10\) clauses in \(N=5\) variables, \[\begin{align} f=&\hphantom{{}\land{}} (\neg v_4\lor \neg v_2\lor v_3)\land (v_2\lor \neg v_4\lor \neg v_5)\land (v_4\lor \neg v_3\lor \neg v_1)\land (v_5\lor v_2\lor v_4)\\ &\land (v_4\lor v_2\lor \neg v_5)\land (v_5\lor \neg v_3\lor \neg v_4)\land (v_1\lor v_2\lor v_3)\land (\neg v_1\lor v_5\lor v_3)\\ &\land (\neg v_3\lor \neg v_5\lor \neg v_4)\land (v_4\lor \neg v_2\lor v_1). \end{align}\] If we would just measure these clauses without dilution, the success probabilities would be \[(p_m)_m = \left(\frac{7}{8},\frac{6}{7},\frac{5}{6},\frac{17}{20},\frac{14}{17},\frac{5}{7},\frac{9}{10},\frac{7}{9},\frac{5}{7},\frac{1}{5}\right),\] which illustrates why the dilution (or a similar technique) is required for the lower bound on the success probability. See also Appendix 3 for a more extreme example. The dilution leads to larger formulas with \(N'=N+M=15\) and \(M'=6 M =60\). A possible instance of the diluted formula is \[\begin{align} \mathcal{D}(f)=&\hphantom{{}\land{}}(\neg v_4\lor \neg v_2\lor v_3\lor \neg v_6)\land (v_4\lor v_6)\land (v_2\lor v_6)\land (\neg v_3\lor v_6)\\ &\land (v_2\lor \neg v_4\lor \neg v_5\lor \neg v_7)\land (\neg v_2\lor v_7)\land (v_4\lor v_7)\land (v_5\lor v_7)\\ &\land (v_4\lor \neg v_3\lor \neg v_1\lor \neg v_8)\land (\neg v_4\lor v_8)\land (v_3\lor v_8)\land (v_1\lor v_8)\\ &\land (v_5\lor v_2\lor v_4\lor \neg v_9)\land (\neg v_5\lor v_9)\land (\neg v_2\lor v_9)\land (\neg v_4\lor v_9)\\ &\land (v_4\lor v_2\lor \neg v_5\lor \neg v_{10})\land (\neg v_4\lor v_{10})\land (\neg v_2\lor v_{10})\land (v_5\lor v_{10})\\ &\land (v_5\lor \neg v_3\lor \neg v_4\lor \neg v_{11})\land (\neg v_5\lor v_{11})\land (v_3\lor v_{11})\land (v_4\lor v_{11})\\ &\land (v_1\lor v_2\lor v_3\lor \neg v_{12})\land (\neg v_1\lor v_{12})\land (\neg v_2\lor v_{12})\land (\neg v_3\lor v_{12})\\ &\land (\neg v_1\lor v_5\lor v_3\lor \neg v_{13})\land (v_1\lor v_{13})\land (\neg v_5\lor v_{13})\land (\neg v_3\lor v_{13})\\ &\land (\neg v_3\lor \neg v_5\lor \neg v_4\lor \neg v_{14})\land (v_3\lor v_{14})\land (v_5\lor v_{14})\land (v_4\lor v_{14})\\ &\land (v_4\lor \neg v_2\lor v_1\lor \neg v_{15})\land (\neg v_4\lor v_{15})\land (v_2\lor v_{15})\land (\neg v_1\lor v_{15})\\ &\land (v_{10}\veebar v_{11}\veebar v_{12}\veebar v_{13}\veebar v_{14}\veebar v_7\veebar v_8)\\ &\land \neg (v_{11}\veebar v_{14}\veebar v_8\veebar v_9)\\ &\land (v_{12}\veebar v_{13}\veebar v_{14}\veebar v_{15}\veebar v_8)\\ &\land \neg (v_{10}\veebar v_{11}\veebar v_8\veebar v_9)\\ &\land (v_{12}\veebar v_{13}\veebar v_{14}\veebar v_7\veebar v_8)\\ &\land (v_{11}\veebar v_{12}\veebar v_{15}\veebar v_7\veebar v_9)\\ &\land \neg (v_{10}\veebar v_{11}\veebar v_{12}\veebar v_9\veebar \neg v_6)\\ &\land \neg (v_{11}\veebar v_{12}\veebar v_{15}\veebar v_7\veebar v_8\veebar v_9)\\ &\land \neg (v_{12}\veebar v_{15}\veebar v_7\veebar v_8\veebar \neg v_6)\\ &\land (v_{14}\veebar v_{15}\veebar v_9\veebar \neg v_6)\\ &\land v_6\land v_7\land v_8\land v_9\land v_{10}\land v_{11}\land v_{12}\land v_{13}\land v_{14}\land v_{15}. \end{align} \label{eq:exampledilution}\tag{8}\] 3 shows which assignments are removed from the solution set by adding these XOR clauses.

We numerically estimate the average success probabilities for the diluted formula as \[\begin{align} (p_m')_m =& (0.9375, 0.733333, 0.818182, 0.888889,\\ &0.9375, 0.733333, 0.818182, 0.888889,\\ &0.9375, 0.733333, 0.818182, 0.888889,\\ &0.9375, 0.733333, 0.818182, 0.888889,\\ &0.9375, 0.733333, 0.818182, 0.888889,\\ &0.9375, 0.733333, 0.818182, 0.888889,\\ &0.9375, 0.733333, 0.818182, 0.888889, \\ &0.9375, 0.733333, 0.818182, 0.888889,\\ &0.9375, 0.733333, 0.818182, 0.888889,\\ &0.9375, 0.733333, 0.818182, 0.888889,\\ &0.515088, 0.53246, 0.570157, 0.653825, 0.765144,\\ &0.860789, 0.92324, 0.960468, 0.980077, 0.9899,\\ &0.998856, 0.998448, 0.998458, 0.998664, 0.998874,\\ &0.999162, 0.999452, 0.999427, 0.999433, 0.99928). \end{align}\] This numerically confirms that the success probability for each measurement is larger than \(\frac{1}{2}\).

We now show the action of \(\mathcal{N}\). Let us assume that we already successfully measured until the 42^nd clause \(C_{42}'\). Then \(e=\bigwedge_{i=1}^{42} C_i'\). At this stage the state is \[\begin{align} \ket{\psi_{42}}=&\frac{1}{\sqrt{10}}(\hphantom{{}+{}} \ket{000011111010111} + \ket{000111011110111} + \ket{010001111111110}\\ &\hphantom{\frac{1}{\sqrt{10}}( }+ \ket{010011111111110} + \ket{010100111111111} + \ket{010110111111111}\\ &\hphantom{\frac{1}{\sqrt{10}}( }+ \ket{011001111111110} + \ket{011011111111110} + \ket{110011111111111}\\ &\hphantom{\frac{1}{\sqrt{10}}( }+ \ket{110110111111111}). \end{align}\] Assume that next we obtain the outcome \(\Pi(\lnot C_{43}')\), projecting onto the state \[\begin{align} \ket{\nu} =&\frac{1}{\sqrt{6}}(\hphantom{{}+{}} \ket{000011111010111} +\ket{000111011110111} +\ket{010001111111110}\\ &\hphantom{\frac{1}{\sqrt{6}}(}+\ket{010011111111110} +\ket{011001111111110} +\ket{011011111111110}). \end{align}\] We lost the amplitude for the solution of \(f\). But we recover by measuring \(\mathcal{N}(e)\). \[\begin{align} {2} P_0(e) Q_y P_0(e) \ket{\nu} =& P_0(e) Q_y \ket{\nu}\\ =& P_0(e) \ket{\pm}^{\otimes N'}\\ =& \ket{\psi_{42}}. \quad\text{(up to phases)} \end{align}\] At this point we can try to measure \(C_{43}'\) again. Note, however, since this is a random XOR-clause, it will most likely take a different value.

6 Robustness of the main results↩︎

In the main text the results are formulated w.r.t. exact operations. Most importantly only the exact implementation of \(\mathcal{N}(F)\) is considered. Thus only the unobservability of this exact operation is proven. However, in reality any measurement is only implemented approximately anyways, as only a finite precision is achievable in any experiment. It is therefore important to look at the robustness of our main results when considering approximate implementations of the discussed operations. In this appendix, we provide some comments on this topic, while we must defer a precise treatment to subsequent work.

Let \(L = R m\) be the maximal number of operations in the algorithm. We now describe why any measurement that is \(\epsilon/L\) close to the sandwich-POVM allows to solve F in polynomial time within an error \(\epsilon\).

There is a ball around the ideal sandwich-POVM of approximate sandwich-POVMs which are also not observable. In this sense our result is robust.

This consideration translates to the consequences discussed in the second part of the main paper. Most importantly, any quantum operation close to the unitary channel \(t(\rho)=U\rho U^{\dagger}\) cannot correspond to a physical quantum operation, because they would allow to implement \(\mathcal{N}\) approximately, which is not possible as discussed above. This also implies that the map from \(\rho\) to \(\tilde{\rho}\) cannot be implemented approximately.

References↩︎