It does matter, because there is more at stake than whether or not we can find solutions. Also of interest is whether we can verify solutions. Other qualitiative distinctions can be made between the ...

If $\mathsf{NP} = \mathsf{PSPACE}$, this would imply: $\mathsf{P^{\#P}} = \mathsf{NP}$That is, counting the solutions to a problem in $\mathsf{NP}$ would be polytime reducible to finding a single ...

I'll echo Martin Schwartz's recommendation of Nielsen & Chaung as the standard reference; there are many others as well. Research in the field prefers to consider uniform families of quantum ...

Scott Aaronson was often fond of pointing out (and probably still is fond of pointing out, assuming he hasn't gotten tired of doing so) that physical processes do not always find the global minimum of ...

Let me provide you with an algorithm for recursively constructing an infinite state machine to decide any language $L \subseteq \{0,1\}^\ast$ that you like. Make the initial state accept if the empty ...

As an introductory reference to the notion of a complexity operator (and demonstrating some applications of the idea), the best I have found so far is D. Kozen, Theory of Computation (Springer ...

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

In a pure mathematical sense, you could in principle create models of computation using any sort of recursively composable structure, so long as you can describe how it represents a transformation of ...

[Revised.] I think that there has been a little confusion about what I was referring to in my original answer. I am revising it in order to better describe the result. Note that your representation ...

Seeing how this question doesn't appear to be set to be moved to Math.SE (where it would properly belong), I'll answer it here. Multisets are an awkward case of a perfectly natural mathematical ...

Summary. All of these papers misunderstand the notion of quantum superpositions and interference, and lead to analyses which do not conserve probability (i.e. in which the probabilities of ...

I cannot remark on whether the Zoo has a continuous existence on the web or elsewhere. However, there are still some proto-Zoo and Zoo-derived resources available on the web. There seems to be a copy ...

One reason why it might seem strange to you, that we seem to think there is more apparent (or conjectured) power in the randomized reductions from $\mathsf{NP}$ to $\mathsf{UP}$ than the comparable ...

Short answer. For quantum circuits, there is at least one non-limitation result: arbitrary bounded-depth quantum circuits are unlikely to be simulatable with small multiplicative error in the ...

Let $~{\mathrm{PRESARITH}}$ denote the decision problem of the truth of statements in Presburger Arithmetic. As you note, [Fischer+Rabin 1974] (PS manuscript) show that the nondeterministic time ...

It's complicated, and depends on whether you approach quantum computing as a technology or a model of computation; and whether you are interested in universal quantum computation, or a special ...

The essential difference between quantum computation and parallelism is for the most part the same as between randomized computation (e.g. using coin-flips, or some other form of random number ...

Elaborating on Joe's earlier answer: note that $\textrm{FACTORING} \in \mathsf{NP \cap coNP}$. The latter is the second lowest class in the "low" hierarchy: which is to say that $\mathsf{NP^{NP \cap ... View answer Accepted answer 9 votes There is a difficulty with the premise of your question — "when does randomization stops helping within$\mathrm{PSPACE}$— because it suggests that the computational classes$\mathrm{X}$... View answer Accepted answer 9 votes Note that Gödel's Incompleteness Theorems are the following statements: Any formal system which can be used to express arithmetic is either incomplete (there are statements which are neither ... View answer Accepted answer 9 votes I'm happy to say that I think we can answer this question in the affirmative: that is, deciding whether a linear congruence is feasible modulo k is coModkL-complete. We can actually reduce this ... View answer 8 votes An example would be the computation of ground state energy of the Ising model with transverse magnetic fields, as described by [Cubitt+Montenaro-2013]. From the abstract: In this work we ... View answer 8 votes Though we've chatted about this in person before, I'll add this in the hope that this will allow someone else to provide a complete answer. In your process of adding vertices, define a partial ... View answer Accepted answer 7 votes No, there is no decomposition of the entire family$\{F_{2^n}\}_{n\geqslant1}$into a single finite gate-set. Here's why. The QFTs involve only coefficients over$\overline{\mathbb Q}$, the complex ... View answer Accepted answer 7 votes Restrictions on pre-orders You've described that you would like to assert restrictions on a given pre-order: for instance, that specifically$a < b$rather than merely$a \leqslant b$, so that it ... View answer Accepted answer 7 votes Short meta preamble — Despite my misgivings (in particular, despite the comment on meta, I don't really think that this question is parallel to the question of why one should define topologies ... View answer Accepted answer 7 votes If all that you want to do is count the number of cycles, you can do this with 2|S| bits (plus change) worth of space. It seems unlikely that you will be able to do much better unless S or f have some ... View answer Accepted answer 7 votes I don't know if this is an "explanation", but hopefully it is a useful "description". More generally than projective measurements, one always measures an operator. (A projector is a special case of ... View answer Accepted answer 6 votes Summary. Using your favourite$O(n^d)$algorithm for finding a matching in graphs on$O(n)$vertices, there is a simple algorithm using$O(\max\{n^{d+2},n^4\})\$ operations over the reals for ...