<p>As evidenced by the comments from Robin and Tsuyoshi, the notion of monotone circuits does seem to be easily extendable to quantum circuits. </p>

<p>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$. </p>

<p>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)&gt;f(|\psi\rangle)$ there exists an alternate state $|\phi\rangle$ such that $f(|\phi\rangle) &gt; f(|\psi\rangle)$ but for which $f(U|\psi\rangle)&gt;f(U|\phi\rangle)$, and hence the evolution $U$ is not monotonic.</p>

<p>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$.</p>

<p>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 <a href="http://arxiv.org/abs/1011.3245">Aaronson and Arkhipov</a>, though not identical (it's a slightly different scattering problem). Further it contains circuits for <a href="http://arxiv.org/abs/1005.1407">IQP</a>, and hence should not be efficiently simulable classically.</p>

CC BY-SA 3.0
2012-09-18T21:14:40.030Z
(1) I do not think that your notion of “quantum monotone” is a generalization of the notion of monotonicity for classical Boolean functions.  For example, the AND gate is monotone because x_1 ≤ y_1 and x_2 ≤ y_2 imply AND(x_1, x_2) ≤ AND(y_1, y_2), where x_1, x_2, y_1, y_2 ∈ {0,1}.  Note that the comparison is between two inputs or between two outputs, not between input and output.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-18T21:16:02.463Z
(2) Just in case, I did not say that the notion of monotone circuits does not easily extend to quantum circuits (nor did I say that it does).  I just said that compared to the case of reversible circuits, where the notion of monotone circuits is uninteresting, the case of quantum circuits is unclear.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-18T22:34:49.797Z
@TsuyoshiIto: Re (1), I've reworded my answer. Basically I intended f to be the ordering on quantum states, since without some ordering the notion of monotonicity is meaningless. I think in this respect it is a reasonable generalization of the classical notion, but I make no claim that it is the only reasonable generalization (or that it is reasonable with respect to all measures!). Re (2), I know you didn't quite say that, and I've tried to reword that line. I meant that when taken together the comments by you and Robin indicate why an extension is non-trivial.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-18T22:41:20.443Z
As for (1), my point is that no matter what f is (and in particular if f is the Hamming weight function), your notion does not lead to the notion of monotone circuits in the classical case because you are making comparisons between input and output whereas “monotone” in the sense as in classical monotone circuits makes comparisons between inputs or between outputs.  Thanks for the edit for (2).
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-18T22:45:07.210Z
For example, according to your definition, the AND gate would not be monotone because it can decrease the Hamming weight from 1 to 0.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-18T22:55:11.610Z
the aaronson ref is 94 pages. could you narrow it down a little?
vzn
CC BY-SA 3.0
2012-09-18T23:00:31.340Z
@TsuyoshiIto: Yes, I see your point, though this is due to the size mismatch between the input and output. If you give the AND two outputs, then this fixes the problem, but I agree it's not a perfect fit. I guess I could define two orderings (on the input and output) in which case it would match up with the classical definition, but it seems odd that these would not be the same since the space of states is the same for both the input and output.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-18T23:01:38.187Z
@vzn: It shows that the operations performable in linear optics are likely hard to simulate classically, despite not being universal for classical computation.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-18T23:03:17.357Z
No, it is not because of the size mismatch.  It is because your definition makes comparisons between wrong things, as I already pointed out.  Consider the gate which outputs two copies of the AND of two input bits.  It still decreases the Hamming weight from 1 to 0, so it would not be monotone according to your definition.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-18T23:04:10.507Z
@TsuyoshiIto: Actually, just let me think about it for a minute.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-18T23:14:21.053Z
@TsuyoshiIto: I agree with your point. I was making an error. However, I've now adapted the above answer to correct this. Can you check if it makes sense to you now?
Joe Fitzsimons
CC BY-SA 3.0
2012-09-18T23:50:28.550Z
(1) I do not think that the classical meaning of monotonicity has anything to do with the Hamming weight.  (2) I do not know how to prove the claim in the third paragraph, but I can believe it.  (3) As I implied in a comment on the question and Niel de Beaudrap wrote in much more detail, I do not think that restricting the consideration to unitary circuits is justified if our purpose is to define a quantum analogue of the notion of monotone circuits.  But I am fine with agreeing to disagree.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-19T00:17:21.780Z
@TsuyoshiIto: I don't think the Hamming weight is fundamental, just one way to view it. If we want to define a monotone on more than a single bit, then we need an ordering on bit strings. The Hamming weight seems natural, and reduces correctly for AND and OR gates, but equally you could order the bit strings by the associating them with distinct integers. I don't think there is a unique solution here. The claim in the third paragraph just follows from the fact that U, since it is unitary, is a bijection between quantum states.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-19T00:36:12.247Z
@JoeFitzsimons: I think the Hamming weight does figure fairly well in the monotonicity requirement, or (more precisely) that the property of being non-decreasing as you "turn on" bits from zero to one is precisely the notion that computer scientists care about when they refer to monotonic circuits. You could consider variations where the function computed is a non-decreasing function of some real-valued function-of-the-bitstrings, such as your re-indexing proposal; but this is also a significant departure from what computer scientists are interested in except for strongly motivated cases.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-19T00:39:57.420Z
The usual partial order on bit strings (the elementwise comparison) looks much more natural than comparing them by their Hamming weights to me, but if you think that the Hamming weight is natural, I will not argue.  As for the third paragraph, I still have difficulty following your argument, but I guess I am missing something simple and I just need some time and a fresh look at it.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-19T00:48:15.717Z
ok, I mean is there a thm or defn in the aaronson ref in particular you think can be translatable to a monotone analog?
vzn
CC BY-SA 3.0
2012-09-19T00:54:35.370Z
@vzn not really, just that they are similar models. The IQP paper already shows that these circuits should be hard to simulate.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-19T00:55:24.247Z
@NieldeBeaudrap: I agree. I didn't mean to suggest I thought otherwise.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-19T03:44:34.137Z
as for studying fns based on hamming weight, that is highly developed theory in monotone circuits with _slice functions_
vzn
CC BY-SA 3.0
2012-09-21T21:56:04.290Z
@GilKalai: Hope it is helpful.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-18T19:04:05.480Z
2012-09-18T23:12:37.390Z
2012-09-18T23:12:37.390Z
Joe Fitzsimons
<p>you ask basically two questions of widely divergent difficulty, at the frontier of two large fields, ie boolean circuits &amp; QM computing, about the possibility of what is sometimes called a "bridge theorem" in mathematics:</p>

<ul>
<li><p>quantum analog of monotone circuits</p></li>
<li><p>quantum analog of Razborovs thm</p></li>
</ul>

<p>the short candid answer is <em>no</em> or <em>not so far</em>.</p>

<p>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.</p>

<p><a href="http://arxiv.org/pdf/1209.1055.pdf" rel="nofollow">Hardness of approximation for quantum problems</a> by Gharibian and Kempe</p>

<p>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 <em>per se</em> but an idea could be that a quantum circuit or algorithm that solves the monotone <em>function</em> QMSA can be taken as a QM analog.</p>

<p>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. </p>

<p>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</p>

<p><a href="http://www.illc.uva.nl/Research/Dissertations/DS-2006-04.text.pdf" rel="nofollow">Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs</a> by Spalek</p>

<p>however, arguably a better analogous QM computing lower bound would put a lower bound on number of <em>qubit operations</em> or possibly based on "complete" gates like Toffoli gates for a monotone function. am not aware of proofs of this type.</p>

<p>another approach might limit the analysis to special quantum AND and OR gates with extra "ancilla" bits added to make the gates reversible.</p>

CC BY-SA 3.0
2012-09-18T22:18:29.883Z
ps its also interesting to note that razborovs thm involves what are sometimes called "approximator" circuits/gates and approximation hardness is probably/apparently connected to the approximator circuit/gate concept in ways that havent been mapped out....
vzn
CC BY-SA 3.0
2012-09-18T22:42:39.480Z
rather than adding comments, I would worry about the 7 downvotes...
Alessandro Cosentino
CC BY-SA 3.0
2012-09-19T00:33:19.893Z
??? guilty until proven innocent? =)
vzn
CC BY-SA 3.0
2012-09-18T15:39:30.953Z
2012-09-18T16:03:25.603Z
2012-09-18T16:03:25.603Z
vzn
<p>You're really asking two different questions and hoping that there is a single response which answers both: <strong>(1)</strong> What natural notions of quantum monotone circuits are there? <strong>(2)</strong> What would a lattice-based Razborov-style quantum result look like?</p>

<p>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).</p>

<h2>What we want from quantum</h2>

<p>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 <em>sine qua non</em> 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.</p>

<p>What we must do is to consider things in such a way as to remove the standard basis from its traditional privilidged place &mdash; or, in this case, as much as is possible while retaining a meaningful notion of monotonicity.</p>

<h2>A simple model of quantum monotone circuits</h2>

<p>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).</p>

<p>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</p>

<ol>
<li><p>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</p></li>
<li><p>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 \}$.</p></li>
</ol>

<p>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.</p>

<p>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.</p>

<p>For any constant <em>k</em>, one might also consider gate bases including <em>k</em>-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 &lt; k$.
It is not clear how much additional computational power this would give you (nor even in the classical case).</p>

<p>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".</p>

<h2>A quantum variant of Razborov's result</h2>

<p>Consider the <a href="http://gowers.files.wordpress.com/2009/05/razborov2.pdf">exposition by Tim Gowers</a> of the results of <a href="http://tau.ac.il/~nogaa/PDFS/Publications/The%20monotone%20circuit%20complexity%20of%20Boolean%20functions.pdf">Alon &amp; Boppana (1987), Combinatorica <strong>7</strong> pp.&nbsp;1&ndash;22</a> 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 <a href="http://arxiv.org/abs/0911.1696">Quantum Lov&aacute;sz Local Lemma</a>, 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 \;, &amp; \text{ for each $1 \leqslant j \leqslant n$} \\ \text{where }
&amp;\mathcal E_j := \Bigl\{ | \mathbf x \rangle \;:\; \mathbf x \in E_j \Bigr\} ; \\
&amp;U_j : \mathcal H_2^{\otimes n} \to \mathcal H_2^{\otimes n} \text{ a unitary of bounded complexity}.
\end{align*}$$
We allow the <a href="http://en.wikipedia.org/wiki/Quantum_logic#Introduction">quantum-logical</a> 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 &lt;\; 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.</p>

<p>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).</p>

<p>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$. </p>

<ul>
<li><p>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).</p></li>
<li><p>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 <em>absence</em> 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).</p></li>
</ul>

<p>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.</p>

CC BY-SA 3.0
2012-09-19T00:29:22.737Z
your sketch makes me wonder. is there a concept of monotonicity for complex values? maybe will study the real arithmetic circuits papers some more. could it be something simple like $|x|$ < $|y|$? or for a two input complex gate $x_1$ and $x_2$ as inputs, $y$ output, $|y| > |x_1|$ and $|y| > |x_2|$?
vzn
CC BY-SA 3.0
2012-09-21T19:47:09.690Z
Oops, I made a mistake... I planned to give the bounty to Niel, but clicked the wrong place.  I owe you 200 reputations Niel :) .
Gil Kalai
CC BY-SA 3.0
2012-09-21T23:34:45.290Z
Is there some way I can pass it to Niel?
Joe Fitzsimons
CC BY-SA 3.0
2012-09-22T19:23:42.707Z
@Joe, you can put a new bounty on the question and award it to Niel.
Kaveh
CC BY-SA 3.0
2012-09-22T19:28:20.577Z
@Kaveh: Okay, will do. I can't award it for 24 hours, but will award it then.
Joe Fitzsimons
CC BY-SA 3.0
2012-09-18T23:11:45.677Z
2012-09-20T13:55:03.923Z
2012-09-20T13:55:03.923Z
Niel de Beaudrap
<p>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.</p>

<p>My question is simple: Is there a quantum analog for monotone circuits (or more than one)? Is there a quantum Razborov's theorem?</p>

CC BY-SA 3.0
2012-09-11T11:34:21.347Z
Here's my two cents: The leap from classical circuits to quantum circuits can be broken into two steps by adding classical reversible circuits in the middle. Classical reversible circuits are those in which only reversible gates are allowed. For example the Toffoli gate is a universal gate for reversible computation. I don't know how to define the notion of monotone for these circuits. It seems to me that defining monotone classical reversible circuits is a prerequisite for defining monotone quantum circuits.
Robin Kothari
CC BY-SA 3.0
2012-09-11T14:42:45.960Z
(1) A (classical) reversible circuit implements a bijection on {0,1}^n, and clearly the only monotone bijection is the identity mapping.  So I do not think that it is reasonable to define “monotone reversible circuits” in a nontrivial way.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-11T14:43:39.280Z
(2) I am not sure about the quantum case.  If we can define “monotone quantum channels,” then it will be natural to define “monotone quantum circuits” as quantum circuits whose gate set is chosen from monotone quantum channels, just as monotone classical circuits are circuits whose gate set is chosen from monotone functions.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-11T15:23:21.717Z
yes! monotone gates just have AND/OR operations/gates-- just use only those quantum gates. but one can only compute monotone functions which are not "functionally complete". the deeper question is what pattern/constraint this enforces on the qm computation/evolution matrices...? as for a qm analog of razborovs thm, have not heard, but it would be something in the form that enforces a lower bound on # of quantum gates or qubit interactions; havent heard of anything like it in the field.
vzn
CC BY-SA 3.0
2012-09-11T15:47:30.983Z
heres a thorough survey of lower bound techniques/proofs in QM by Spalek, [Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs](http://www.illc.uva.nl/Research/Dissertations/DS-2006-04.text.pdf), which generally look much different than anything in circuit theory. there does seem to be some analog to "computational bandwidth/bottleneck" in direct product theorems (DPTs) which coincidentally razborov has been working on, see p 139. see also [QM DPT vs SAT](http://cstheory.stackexchange.com/questions/12500/are-resource-savings-for-the-evaluation-of-k-dependent-instances-in-parallel-p)
vzn
CC BY-SA 3.0
2012-09-11T16:58:51.810Z
@RobinKothari, TsuyoshiIto: The importance of reversibility to quantum computation comes precisely from the special case of Schrödinger evolution of a closed system. When we speak of AND and OR gates, however, we're considering an abstracted physical system which is a caricature of the logic gates which are in computers; and those gates work precisely because they aren't closed systems. If we allow ourselves to speak of AND and OR gates per se, I think it's quite reasonable to lift the convention of considering closed systems for the quantum computational question as well.
Niel de Beaudrap
CC BY-SA 3.0
2012-09-11T17:41:05.500Z
@Niel de Beaudrap: That is precisely why I separate the issue with reversible circuits and quantum circuits.
Tsuyoshi Ito
CC BY-SA 3.0
2012-09-12T00:03:39.993Z
@Niel, Tsuyoshi: I guess I thought that a monotone quantum circuit would still be a quantum circuit in the traditional sense (i.e., unitaries followed by a measurement). But following Niel's argument, I guess it makes sense to drop that constraint. So my previous comment doesn't really apply then.
Robin Kothari
CC BY-SA 3.0
2012-09-13T04:10:14.543Z
ok, there may be multiple ways to do this. are you guys arguing about dropping the requirement of reversibility? all QM computing is based on reversibility, right? reversibility of conventional gates encoded into QM is handled with ancilla bits. therefore there are AND/OR gates that have addl ancilla bits that make the nonreversible AND/OR reversible, right? as for some other approach using monotone (but not binary) functions as inputs as TI seems to be suggesting, thats a possibility. note there are some thms/papers on lower bounds wrt real valued monotone functions....
vzn
CC BY-SA 3.0
2012-09-19T02:41:53.257Z
another thought. apparently in lower bound complexity theory, monotone circuits were originally meant to be a "relaxation" of the complexity of the full basis, ie a simpler model to study that lower bounds would be more accessable/provable, and largely succeeded in that regard (although a P vs NP proof was/is one of the initial/ultimate goals/motivations). but maybe there is some other "natural" relaxation of QM computing making lower bounds more provable in the QM realm that doesnt look like monotone circuits at all. possibly instead related to matrix algebra. etc. maybe even more than one.
vzn
CC BY-SA 3.0
2012-10-17T01:51:43.413Z
from A.Razborov in email who looked at this page & graciously agreed to share— "My own thoughts on the subject (it was long ago, though, when I last time thought about it) echo those of most people who have contributed to the discussion. We really do not know how to define monotone quantum circuits, and, moreover, the very concept behind QM is as ultimately non-monotone as it gets." ...
vzn
CC BY-SA 3.0
2012-10-17T01:52:27.263Z
(contd...) "Which makes me somewhat
pessimistic that a viable model of monotone QC exists. With all due respect to people who offered directions in which one can try to arrive at such a model, none of these is convincing enough for me to embark on the second part of the project (NP is not doable by monotone QC) :-)"
vzn
<cc.complexity-theory><quantum-computing><circuit-complexity>
A Notion of Monotone Quantum Circuits
Gil Kalai
# A Notion of Monotone Quantum Circuits

(Asked by: username_0 on 2012-09-11)

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?

**Tags:** cc.complexity-theory, quantum-computing, circuit-complexity

> **Comments:**
> **username_1**: Here's my two cents: The leap from classical circuits to quantum circuits can be broken into two steps by adding classical reversible circuits in the middle. Classical reversible circuits are those in which only reversible gates are allowed. For example the Toffoli gate is a universal gate for reversible computation. I don't know how to define the notion of monotone for these circuits. It seems to me that defining monotone classical reversible circuits is a prerequisite for defining monotone quantum circuits.  
> **username_2**: (1) A (classical) reversible circuit implements a bijection on {0,1}^n, and clearly the only monotone bijection is the identity mapping.  So I do not think that it is reasonable to define “monotone reversible circuits” in a nontrivial way.  
> **username_2**: (2) I am not sure about the quantum case.  If we can define “monotone quantum channels,” then it will be natural to define “monotone quantum circuits” as quantum circuits whose gate set is chosen from monotone quantum channels, just as monotone classical circuits are circuits whose gate set is chosen from monotone functions.  
> **username_3**: yes! monotone gates just have AND/OR operations/gates-- just use only those quantum gates. but one can only compute monotone functions which are not "functionally complete". the deeper question is what pattern/constraint this enforces on the qm computation/evolution matrices...? as for a qm analog of razborovs thm, have not heard, but it would be something in the form that enforces a lower bound on # of quantum gates or qubit interactions; havent heard of anything like it in the field.  
> **username_3**: heres a thorough survey of lower bound techniques/proofs in QM by Spalek, [Quantum Algorithms, Lower Bounds, and Time-Space Tradeoffs](http://www.illc.uva.nl/Research/Dissertations/DS-2006-04.text.pdf), which generally look much different than anything in circuit theory. there does seem to be some analog to "computational bandwidth/bottleneck" in direct product theorems (DPTs) which coincidentally razborov has been working on, see p 139. see also [QM DPT vs SAT](http://cstheory.stackexchange.com/questions/12500/are-resource-savings-for-the-evaluation-of-k-dependent-instances-in-parallel-p)  
> **username_4**: @RobinKothari, TsuyoshiIto: The importance of reversibility to quantum computation comes precisely from the special case of Schrödinger evolution of a closed system. When we speak of AND and OR gates, however, we're considering an abstracted physical system which is a caricature of the logic gates which are in computers; and those gates work precisely because they aren't closed systems. If we allow ourselves to speak of AND and OR gates per se, I think it's quite reasonable to lift the convention of considering closed systems for the quantum computational question as well.  
> **username_2**: @username_4: That is precisely why I separate the issue with reversible circuits and quantum circuits.  
> **username_1**: @Niel, Tsuyoshi: I guess I thought that a monotone quantum circuit would still be a quantum circuit in the traditional sense (i.e., unitaries followed by a measurement). But following Niel's argument, I guess it makes sense to drop that constraint. So my previous comment doesn't really apply then.  
> **username_3**: ok, there may be multiple ways to do this. are you guys arguing about dropping the requirement of reversibility? all QM computing is based on reversibility, right? reversibility of conventional gates encoded into QM is handled with ancilla bits. therefore there are AND/OR gates that have addl ancilla bits that make the nonreversible AND/OR reversible, right? as for some other approach using monotone (but not binary) functions as inputs as TI seems to be suggesting, thats a possibility. note there are some thms/papers on lower bounds wrt real valued monotone functions....  
> **username_3**: another thought. apparently in lower bound complexity theory, monotone circuits were originally meant to be a "relaxation" of the complexity of the full basis, ie a simpler model to study that lower bounds would be more accessable/provable, and largely succeeded in that regard (although a P vs NP proof was/is one of the initial/ultimate goals/motivations). but maybe there is some other "natural" relaxation of QM computing making lower bounds more provable in the QM realm that doesnt look like monotone circuits at all. possibly instead related to matrix algebra. etc. maybe even more than one.  
> **username_3**: from A.Razborov in email who looked at this page & graciously agreed to share— "My own thoughts on the subject (it was long ago, though, when I last time thought about it) echo those of most people who have contributed to the discussion. We really do not know how to define monotone quantum circuits, and, moreover, the very concept behind QM is as ultimately non-monotone as it gets." ...  
> **username_3**: (contd...) "Which makes me somewhat pessimistic that a viable model of monotone QC exists. With all due respect to people who offered directions in which one can try to arrive at such a model, none of these is convincing enough for me to embark on the second part of the project (NP is not doable by monotone QC) :-)"  

---

## 3 answers

### Answer by username_4 on 2012-09-18. Score: 20 | Accepted answer

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).

## What we want from quantum

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.

## A simple model of quantum monotone circuits

Consider a circuit model which is implicit in username_2'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

1. 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
2. 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".

## A quantum variant of Razborov's result

Consider the [exposition by Tim Gowers](http://gowers.files.wordpress.com/2009/05/razborov2.pdf) of the results of [Alon & Boppana (1987), Combinatorica **7** pp. 1–22](http://tau.ac.il/~nogaa/PDFS/Publications/The%20monotone%20circuit%20complexity%20of%20Boolean%20functions.pdf) 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](http://arxiv.org/abs/0911.1696), 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](http://en.wikipedia.org/wiki/Quantum_logic#Introduction) 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.

> **Comments:**
> **username_3**: your sketch makes me wonder. is there a concept of monotonicity for complex values? maybe will study the real arithmetic circuits papers some more. could it be something simple like $|x|$ < $|y|$? or for a two input complex gate $x_1$ and $x_2$ as inputs, $y$ output, $|y| > |x_1|$ and $|y| > |x_2|$?  
> **username_0**: Oops, I made a mistake... I planned to give the bounty to Niel, but clicked the wrong place.  I owe you 200 reputations Niel :) .  
> **username_5**: Is there some way I can pass it to Niel?  
> **username_7**: @Joe, you can put a new bounty on the question and award it to Niel.  
> **username_5**: @username_7: Okay, will do. I can't award it for 24 hours, but will award it then.  

---

### Answer by username_5 on 2012-09-18. Score: 8

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](http://arxiv.org/abs/1011.3245), though not identical (it's a slightly different scattering problem). Further it contains circuits for [IQP](http://arxiv.org/abs/1005.1407), and hence should not be efficiently simulable classically.

> **Comments:**
> **username_2**: (1) I do not think that your notion of “quantum monotone” is a generalization of the notion of monotonicity for classical Boolean functions.  For example, the AND gate is monotone because x_1 ≤ y_1 and x_2 ≤ y_2 imply AND(x_1, x_2) ≤ AND(y_1, y_2), where x_1, x_2, y_1, y_2 ∈ {0,1}.  Note that the comparison is between two inputs or between two outputs, not between input and output.  
> **username_2**: (2) Just in case, I did not say that the notion of monotone circuits does not easily extend to quantum circuits (nor did I say that it does).  I just said that compared to the case of reversible circuits, where the notion of monotone circuits is uninteresting, the case of quantum circuits is unclear.  
> **username_5**: @TsuyoshiIto: Re (1), I've reworded my answer. Basically I intended f to be the ordering on quantum states, since without some ordering the notion of monotonicity is meaningless. I think in this respect it is a reasonable generalization of the classical notion, but I make no claim that it is the only reasonable generalization (or that it is reasonable with respect to all measures!). Re (2), I know you didn't quite say that, and I've tried to reword that line. I meant that when taken together the comments by you and Robin indicate why an extension is non-trivial.  
> **username_2**: As for (1), my point is that no matter what f is (and in particular if f is the Hamming weight function), your notion does not lead to the notion of monotone circuits in the classical case because you are making comparisons between input and output whereas “monotone” in the sense as in classical monotone circuits makes comparisons between inputs or between outputs.  Thanks for the edit for (2).  
> **username_2**: For example, according to your definition, the AND gate would not be monotone because it can decrease the Hamming weight from 1 to 0.  
> **username_3**: the aaronson ref is 94 pages. could you narrow it down a little?  
> **username_5**: @TsuyoshiIto: Yes, I see your point, though this is due to the size mismatch between the input and output. If you give the AND two outputs, then this fixes the problem, but I agree it's not a perfect fit. I guess I could define two orderings (on the input and output) in which case it would match up with the classical definition, but it seems odd that these would not be the same since the space of states is the same for both the input and output.  
> **username_5**: @username_3: It shows that the operations performable in linear optics are likely hard to simulate classically, despite not being universal for classical computation.  
> **username_2**: No, it is not because of the size mismatch.  It is because your definition makes comparisons between wrong things, as I already pointed out.  Consider the gate which outputs two copies of the AND of two input bits.  It still decreases the Hamming weight from 1 to 0, so it would not be monotone according to your definition.  
> **username_5**: @TsuyoshiIto: Actually, just let me think about it for a minute.  
> **username_5**: @TsuyoshiIto: I agree with your point. I was making an error. However, I've now adapted the above answer to correct this. Can you check if it makes sense to you now?  
> **username_2**: (1) I do not think that the classical meaning of monotonicity has anything to do with the Hamming weight.  (2) I do not know how to prove the claim in the third paragraph, but I can believe it.  (3) As I implied in a comment on the question and username_4 wrote in much more detail, I do not think that restricting the consideration to unitary circuits is justified if our purpose is to define a quantum analogue of the notion of monotone circuits.  But I am fine with agreeing to disagree.  
> **username_5**: @TsuyoshiIto: I don't think the Hamming weight is fundamental, just one way to view it. If we want to define a monotone on more than a single bit, then we need an ordering on bit strings. The Hamming weight seems natural, and reduces correctly for AND and OR gates, but equally you could order the bit strings by the associating them with distinct integers. I don't think there is a unique solution here. The claim in the third paragraph just follows from the fact that U, since it is unitary, is a bijection between quantum states.  
> **username_4**: @JoeFitzsimons: I think the Hamming weight does figure fairly well in the monotonicity requirement, or (more precisely) that the property of being non-decreasing as you "turn on" bits from zero to one is precisely the notion that computer scientists care about when they refer to monotonic circuits. You could consider variations where the function computed is a non-decreasing function of some real-valued function-of-the-bitstrings, such as your re-indexing proposal; but this is also a significant departure from what computer scientists are interested in except for strongly motivated cases.  
> **username_2**: The usual partial order on bit strings (the elementwise comparison) looks much more natural than comparing them by their Hamming weights to me, but if you think that the Hamming weight is natural, I will not argue.  As for the third paragraph, I still have difficulty following your argument, but I guess I am missing something simple and I just need some time and a fresh look at it.  
> **username_3**: ok, I mean is there a thm or defn in the aaronson ref in particular you think can be translatable to a monotone analog?  
> **username_5**: @username_3 not really, just that they are similar models. The IQP paper already shows that these circuits should be hard to simulate.  
> **username_5**: @NieldeBeaudrap: I agree. I didn't mean to suggest I thought otherwise.  
> **username_3**: as for studying fns based on hamming weight, that is highly developed theory in monotone circuits with _slice functions_  
> **username_5**: @GilKalai: Hope it is helpful.  

---

### Answer by username_3 on 2012-09-18. Score: -5

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](http://arxiv.org/pdf/1209.1055.pdf) 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](http://www.illc.uva.nl/Research/Dissertations/DS-2006-04.text.pdf) 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.

> **Comments:**
> **username_3**: ps its also interesting to note that razborovs thm involves what are sometimes called "approximator" circuits/gates and approximation hardness is probably/apparently connected to the approximator circuit/gate concept in ways that havent been mapped out....  
> **username_6**: rather than adding comments, I would worry about the 7 downvotes...  
> **username_3**: ??? guilty until proven innocent? =)  

---

