Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
In computational complexity there is an important distinction between monotone and general computations and a famous theorem by Razborov asserts that 3-SAT and even MATCHING are not polynomial in the monotone Boolean circuits model.
My question is simple: Is there a quantum analog for monotone circuits (or more than one)? Is there a quantum Razborov's theorem?
You're really asking two different questions and hoping that there is a single response which answers both: (1) What natural notions of quantum monotone circuits are there? (2) What would a lattice-based Razborov-style quantum result look like?
It isn't obvious how to achieve both at the same time, so I'll describe what to me seems a reasonable notion of quantum monotonic circuits (without indicating whether or not there is a corresponding Razborov result), and a completely different notion of what a "natural" quantum Razborov conjecture would look like (without indicating whether it is likely to be true).
As I remark in the comments, I think that it is not necessary to try to squeeze the notion of monotonic circuits into a mold of unitarity. Whether it is in the fact that evolution with time need not preserve the standard basis, or in the fact that there exists multiple bases of measurement in which the outcomes may be entangled, I think the sine qua non of quantum computation is the fact that the standard basis is not the only basis. Even among the product states, it is in some implementations defined only by a choice of frame of reference.
What we must do is to consider things in such a way as to remove the standard basis from its traditional privilidged place — or, in this case, as much as is possible while retaining a meaningful notion of monotonicity.
Consider a circuit model which is implicit in Tsuyoshi Ito's comment about "monotone quantum channels" (and which is pretty much what one must do if one wants a notion of "a circuit" which is not restricted to unitary evolution).
Let $\mathbf H$ be the space of Hermitian operators on $\mathbb C^2$ (so that it contains all density operators on one qubit). How would we define a quantum monotone gate $\mathsf G: \mathbf H_a \otimes \mathbf H_b \to \mathbf H_c$ from two input qubits $a,b$ to an output qubit $c$, in such a way that it isn't effectively a classical monotone gate? I think it's straightforward to say that the output should not be restricted to $|0\rangle\!\langle 0|$ or $|1\rangle\!\langle 1|$, or mixtures of them; bu that to be "monotone", we should require that as $\langle 1 | \,\mathop{\mathrm{Tr}_a}\bigl(\rho_{ab}\bigr) |1\rangle$ and $\langle 1 | \,\mathop{\mathrm{Tr}_b}\bigl(\rho_{ab}\bigr) |1\rangle$ increase, the value of $\langle 1 | \mathsf G(\rho_{ab}) | 1 \rangle$ must be non-decreasing. For a two-input-qubit gate, this means that $\mathsf G$ must be implementable in principle as
performing a two-qubit measurement with respect to some orthonormal basis $\{ |00\rangle, |\mu\rangle, |\nu\rangle, |11\rangle \}$, where $|\mu\rangle,|\nu\rangle$ span the subspace of Hamming weight 1, and
producing as output some state $\rho \in \{ \rho_{00}, \rho_\mu, \rho_\nu, \rho_{11} \}$ corresponding to the outcome it measured, where $\langle 1 | \rho_{00} | 1 \rangle \leqslant \langle 1 | \rho_\lambda | 1 \rangle \leqslant \langle 1 | \rho_{11} | 1 \rangle$ for each $\lambda \in \{ \mu, \nu \}$.
The circuits are just compositions of these in the sensible way. We might also allow fan-out, in the form of circuits which unitarily embed $|0\rangle \mapsto |00\cdots 0\rangle$ and $|1\rangle \mapsto |11\cdots 1\rangle$; we should at the very least permit these maps at the input, to allow each (nominally classical) input bit to be copied.
It seems reasonable either to consider the entire continuum of such gates, or to restrict to some finite collection of such gates. Any choice gives rise to a different "quantum monotone gate basis" for the circuits; one can consider what properties different monotone bases have. The states $\rho_{00}, \rho_\mu, \rho_\nu, \rho_{11}$ can be chosen completely independently, subject to the monotonicity constraint; it would undoubtedly be interesting (and probably practical to bound error) to set $\rho_{00} = |0\rangle\!\langle 0|$ and $\rho_{11} = |1\rangle\!\langle 1|$, though I see no reason to require this in the theory. Obviously AND and OR are gates of this type, where $\rho_\mu = \rho_\nu = |0\rangle\!\langle 0|$ and $\rho_\mu = \rho_\nu = |1\rangle\!\langle 1|$ respectively, whatever one chooses $|\mu\rangle$ or $|\nu\rangle$ to be.
For any constant k, one might also consider gate bases including k-input-one-output gates. The simplest approach in this case would probably be to allow gates $\mathsf G: \mathbf H^{\otimes k} \to \mathbf H$ which may be implemented as above, allowing any decomposition of the subspaces $\mathcal V_w \leqslant \mathcal H_2^{\otimes k}$ of each Hamming weight $0 \leqslant w \leqslant k$, and to require that $$ \max_{|\psi\rangle \in \mathcal V_w}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle \;\;\leqslant\;\; \min_{|\psi\rangle \in \mathcal V_{w+1}}\;\langle 1 | \,\mathsf G\Bigl( |\psi\rangle\!\langle\psi| \Bigr)\, |1\rangle $$ for each $0 \leqslant w < k$. It is not clear how much additional computational power this would give you (nor even in the classical case).
I don't know whether there's anything interesting to say about such circuits beyond the classical case, but this seems to me to be the most promising candidate definition of a "quantum monotone circuit".
Consider the exposition by Tim Gowers of the results of Alon & Boppana (1987), Combinatorica 7 pp. 1–22 which strengthen Razborov's results (and makes explicit some of his techniques) for the monotone complexity of CLIQUE. Gowers presents this in terms of a recursive construction of a family of sets, staring from the "half-spaces" $$E_j = \Bigl\{ \mathbf x \in \{0,1\}^n \;:\; x_j = 1 \Bigr\}$$ of the boolean cube for each $1 \leqslant j \leqslant n$. If we remove the priviledged position of the standard basis in the base sets, in analogy to the Quantum Lovász Local Lemma, we may consider a subspace of $\mathcal H_2^{\otimes n}$ to correspond to a binary proposition (whether a state belongs to the subspace, or is instead orthogonal to it) which might arise from measurement. For instance, we may consider $n$ subspaces $\mathcal A_j \leqslant \mathcal H_2^{\otimes n}$ given by $$\begin{align*} \mathcal A_j = U_j \mathcal E_j \;, & \text{ for each $1 \leqslant j \leqslant n$} \\ \text{where } &\mathcal E_j := \Bigl\{ | \mathbf x \rangle \;:\; \mathbf x \in E_j \Bigr\} ; \\ &U_j : \mathcal H_2^{\otimes n} \to \mathcal H_2^{\otimes n} \text{ a unitary of bounded complexity}. \end{align*}$$ We allow the quantum-logical analogues of conjunction and disjunction of subspaces: $$\begin{gather*} \mathcal A \wedge \mathcal B = \mathcal A \cap \mathcal B ; \\ \mathcal A \vee \mathcal B = \mathcal A + \mathcal B = \Bigl\{ \mathbf a + \mathbf b \,:\, \mathbf a \in \mathcal A\;,\; \mathbf b \in \mathcal B \Bigr\} . \end{gather*}$$ We then ask how long a recursive construction of conjunctions and disjunctions of spaces are required to obtain a space $C$, such that the projector $\Pi_C$ onto $C$ differs only slightly from the projector $\Pi_{K(r)}$ onto the space spanned by the indicator functions of graphs having cliques of size $r$; for instance, so that $\| \Pi_C - \Pi_{K(r)} \|_\infty <\; 1/\mathrm{poly}(n) $. The monotonic part is involved in the quantum logical operations, and the primitive propositions about the input are quantum as well.
In the general case, there is a problem with treating this as a computational problem: the disjunction doesn't correspond to any knowledge which could be obtained with certainty by measurements on a finite number of copies using black-box measurements for $\mathcal A$ and $\mathcal B$ alone, unless they are the images of commuting projectors. This general problem can still be treated as an interesting result about geometrico-combinatorical complexity, and might give rise to results related to frustrated local Hamiltionians. However, it might be more natural to just require that the subspaces $\mathcal A_j$ arise from commuting projectors, in which case the disjunction is just the classical OR of the measurement outcomes of those projectors. Then we may require that the unitaries $U_j$ all be the same, and this becomes a problem about a unitary circuit (which gives rise to the "primitive events") with monotone classical post-processing (which performs the logical operations on those events).
Note also that if we do not impose any further restrictions on the spaces $\mathcal A_j$, it may being a subspace with very high overlap with some space $\mathcal E_k^\bot$ spanned by standard basis states $\mathbf x \in \bar E_k$, which are those binary strings in which $x_k = 0$.
If this possibility makes you squeamish, you can always require that $\mathcal A_j$ has an angle of separation from any $\mathcal E_k^\bot$ of at least $\frac{\pi}{2} - 1/\mathrm{poly}(n)$ (so that our primitive subspaces are, at worst, approximately unbiased from the subspaces in which one of the bits is set to 1).
If we don't impose such a restriction, it seems to me that admitting subspaces having high overlap with $\mathcal E_k^\bot$ would be an obstacle to approximating CLIQUE(r) anyway; either we would be more-or-less restricted to considering the absence of a particular edge (rather than its presence), or we would be forced to ignore one of the edges altogether. So, I do not see it as terribly important to impose any restrictions on $\mathcal A_j$, except possibly that they all are the images of a commuting set of projectors, if one's goal is to consider how to "monotonically evaluate CLIQUE from simple quantum propositions". At worst, it would amount classically to allowing NOT gates at the input (and having all fan-out occur after the negation).
Again, it is not clear to me whether substituting the base sets with arbitrary subspaces of $\mathcal H_2^{\otimes n}$ gives rise to a more interesting problem than just using the subspaces $\mathcal E_j$; though if we restrict ourselves to the case of CNF formulae (either in the commuting or the non-commuting case), the results we obtain would correspond to some notion of complexity of a frustration-free Hamiltonian whose ground-state manifold consisted of standard basis states representing cliques.
As evidenced by the comments from Robin and Tsuyoshi, the notion of monotone circuits does seem to be easily extendable to quantum circuits.
In order to have a meaningful definition of quantum monotone circuit, we need to pick an ordering on quantum states with respect to which the monotonicity is defined. Classically a reasonable option (and one which leads to the normal notion of monotonic circuits), is the Hamming weight, but let's consider an ordering given by an arbitrary function $f$.
Since the evolution of a closed quantum system is unitary (which we can assume is given by $U$), then for every state $|\psi\rangle$ such that $f(U|\psi\rangle)>f(|\psi\rangle)$ there exists an alternate state $|\phi\rangle$ such that $f(|\phi\rangle) > f(|\psi\rangle)$ but for which $f(U|\psi\rangle)>f(U|\phi\rangle)$, and hence the evolution $U$ is not monotonic.
Thus the only circuits which are monotonic with respect to $f$ are those which $f(U|\psi\rangle)=f(|\psi\rangle)$ for all $|\psi\rangle$. Thus any gate set which is monotonic with respect to $f$ is composed of gates which commute with $f$.
Obviously, the sets of gates which can satisfy this depend on the definition of $f$. If $f$ is constant, then all gates sets are monotonic with respect to it. However, if we choose $f$ as the Hamming weight of states in the computational basis (a somewhat natural extension of the $f$ used in the classical case), we get an interesting structure. The restriction imposed requires that the Hamming weight remains unchanged. The operations which preserve this amount to either diagonal operations or partial SWAPs, or combinations of these. This structure shows up quite often in physics (in tight binding models etc.), and is similar to the Boson scattering problem studied by Aaronson and Arkhipov, though not identical (it's a slightly different scattering problem). Further it contains circuits for IQP, and hence should not be efficiently simulable classically.
you ask basically two questions of widely divergent difficulty, at the frontier of two large fields, ie boolean circuits & QM computing, about the possibility of what is sometimes called a "bridge theorem" in mathematics:
quantum analog of monotone circuits
quantum analog of Razborovs thm
the short candid answer is no or not so far.
for (1), not as hard a question, but still apparently rarely considered, did turn up the following reference which could be taken as a related case in the literature.
Hardness of approximation for quantum problems by Gharibian and Kempe
they consider some "monotone" problems in a quantum context eg QMSA, "Quantum Monotone Minimum Satisfying Assignment, QMSA", ie a SAT QM analog; (also another problem Quantum Monotone Minimum Weight Word, QMW) and show some approximation hardness results, ie lower bounds. they dont consider monotone quantum circuits per se but an idea could be that a quantum circuit or algorithm that solves the monotone function QMSA can be taken as a QM analog.
as for (2) it would be a very advanced result if it existed which it does not seem to "so far". Razborov's thm is basically a lower bound "bottleneck" type result considered a distinct breakthrough and near-unrivalled result in (monotone) circuit theory.
so roughly speaking yes of course there are some lower bound bottlenecks found in QM computing, eg related to direct product theorems, for a survey see eg
Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs by Spalek
however, arguably a better analogous QM computing lower bound would put a lower bound on number of qubit operations or possibly based on "complete" gates like Toffoli gates for a monotone function. am not aware of proofs of this type.
another approach might limit the analysis to special quantum AND and OR gates with extra "ancilla" bits added to make the gates reversible.
