29
$\begingroup$

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?

$\endgroup$
12
  • 11
    $\begingroup$ 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. $\endgroup$ Sep 11, 2012 at 11:34
  • 6
    $\begingroup$ (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. $\endgroup$ Sep 11, 2012 at 14:42
  • 3
    $\begingroup$ (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. $\endgroup$ Sep 11, 2012 at 14:43
  • 2
    $\begingroup$ @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. $\endgroup$ Sep 11, 2012 at 16:58
  • 3
    $\begingroup$ @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. $\endgroup$ Sep 12, 2012 at 0:03

3 Answers 3

19
+200
$\begingroup$

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

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

$\endgroup$
5
  • $\begingroup$ 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|$? $\endgroup$
    – vzn
    Sep 19, 2012 at 0:29
  • $\begingroup$ Oops, I made a mistake... I planned to give the bounty to Niel, but clicked the wrong place. I owe you 200 reputations Niel :) . $\endgroup$
    – Gil Kalai
    Sep 21, 2012 at 19:47
  • $\begingroup$ Is there some way I can pass it to Niel? $\endgroup$ Sep 21, 2012 at 23:34
  • $\begingroup$ @Joe, you can put a new bounty on the question and award it to Niel. $\endgroup$
    – Kaveh
    Sep 22, 2012 at 19:23
  • $\begingroup$ @Kaveh: Okay, will do. I can't award it for 24 hours, but will award it then. $\endgroup$ Sep 22, 2012 at 19:28
7
+200
$\begingroup$

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.

$\endgroup$
20
  • 1
    $\begingroup$ (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. $\endgroup$ Sep 18, 2012 at 21:14
  • $\begingroup$ (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. $\endgroup$ Sep 18, 2012 at 21:16
  • 1
    $\begingroup$ @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. $\endgroup$ Sep 19, 2012 at 0:36
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 19, 2012 at 0:39
  • 1
    $\begingroup$ @NieldeBeaudrap: I agree. I didn't mean to suggest I thought otherwise. $\endgroup$ Sep 19, 2012 at 0:55
-6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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.... $\endgroup$
    – vzn
    Sep 18, 2012 at 22:18
  • 6
    $\begingroup$ rather than adding comments, I would worry about the 7 downvotes... $\endgroup$ Sep 18, 2012 at 22:42
  • 2
    $\begingroup$ ??? guilty until proven innocent? =) $\endgroup$
    – vzn
    Sep 19, 2012 at 0:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.