The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Tag Info

Hot answers tagged complexity-theory

7

There is evidently a classical polynomial-time algorithm for finding a four-coloring of a given planar graph, so the answer to the question is "yes" for the trivial reason that every polynomial-time classical algorithm can be implemented as a polynomial-time quantum algorithm. (Also, polynomial time implies polynomial space, for both quantum and classical ...

7

The essential feature of this problem is that while both the quantum and classical algorithms can make use of the efficient classical function of calculating $a^k\text{ mod }N$, the issue is how many times does each have to evaluate the function. For the classical algorithm you're suggesting, you'd calculate $a\text{ mod }N$, and $a^2\text{ mod }N$, and $a^... 6 I believe there are two issues here. The first isn't anything wrong with your statement, but rather that you could make a far stronger (non-quantum) statement by the same reasoning:$\mathsf{P}\neq \mathsf{BPP}$. Why is this? For testing if an$n$bit function is constant or balanced with certainty (as required by$\mathsf{P}$), it could be that we have to ... 5 To determine the classical complexity of a problem you need two things, of course: an upper bound (generally an algorithm) and a lower bound. There is an easy randomized algorithm that works with high probability given$O(2^{n/2})$queries to the function$f$: for a suitable constant$c>0$, generate$k = c 2^{n/2}$strings$x_1,\ldots,x_k\in\{0,1\}^n$... 4 Yes. Computing this matrix is something we call Hamiltonian Simulation. We do not use the verb "simulate" alone though I think. It is the norm. I think you assume in general they use either the max norm, which is the largest entry of the Hamiltonian, or the norm is referring to the largest eigenvalue in absolute value (which is called the spectral radius ... 4 It seems this problem is open. Watrous [J. Comp. Sys. Sci. 59, (pp. 281-326), 1999] proved that any space$s$bounded quantum Turing Machine (for space constructible$s(n)>\Omega(\log n)$) can be simulated by deterministic Turing machine with$O(s^2)$space. With the assumption$\mathsf{P \neq SC}$(where$\mathsf{SC \subseteq P}$is defined as ... 4 There are two notions of Zeno topics related to quantum computation. The first, which is controversial is usually called hypercomputation, which deals with the possibility of surpassing the limitations of the Church-Turing thesis by means of quantum computation. It is related to the Zeno effect through the fact that if it could be realized, it may solve the ... 4 Since$\mathsf{BQP}$can be defined on different universal gate sets due to the Solovay-Kitaev theorem, we can choose Hadamard gate$\operatorname{H}$and Toffoli gate$\operatorname{CCNOT}$as a gate set, like Scott Aaronson's definition of$\mathsf{PostBQP}$mentioned in the following: Here ‘uniform’ means that there exists a classical algorithm that ... 4 I think the idea of the proof is that if$|h\rangle$can be shown to be orthogonal to$|\mathcal H\rangle$then it would imply that that$h \not\in \mathcal{H}$. Otherwise,$h\in \mathcal{H}$. Not really as far as the method shown in the linked video is concerned. The algorithm described there uses a controlled-unitary operation of the form $$\newcommand{\... 4 I just recently have been watching a series great YouTube lectures by Ryan O'Donnell at Carnegie Mellon. The last one in particular has some answers to the above question - especially the last 10 minutes or so. I will summarize my limited understanding. Misunderstandings are my own... A "closed timelike curve" (CTC) may be something akin to a wormhole in ... 3 As an initial matter, let's ask "what is the classical computational complexity of solving 'mate-in-n' type games?" For example, is it even in \mathcal{NP} to know, given a certain chess position, that white can mate in 10 or fewer moves? It's been known for a while that we can consider such questions as a "quantified boolean formula" (QBF) question. ... 3 Define the states$$ |\psi_t\rangle=\left\{\begin{array}{cc} |t\rangle\otimes(U_{t-1}U_{t-2}\ldots U_1|\psi\rangle) & t=1,2,\ldots T \\ |t\rangle\otimes(U_{T}U_{T-1}\ldots U_1|\psi\rangle) & t=T+1,T+2,\ldots 2T \\ |t\rangle\otimes(U_{3T+1-t}U_{3T-t}\ldots U_1|\psi\rangle) & t=2T+1,2T+2,\ldots 3T \end{array}\right. $$Now let$$ U=\frac{2}{T}\sum_{... 3 As to the question of how to convert a function performed iteratively using irreversible gates to the same function performed iteratively using reversible gates, you should probably accept that any boolean function from$\{0,1\}^n$to$\{0,1\}$can be written in$\mathsf{3CNF}$-normal form with a polynomial number of$\mathsf{AND, OR, NOT}$gates (i.e.$\lor$... 3 DaftWullie's comments aren't special to 'efficiently computable' functions$f(x)$— any function at all which we know how to compute by conventional means, we can compute reversibly with at most a (small!) constant factor overhead. How to reversibly compute a function The proof is simple. For any procedure to compute something conventionally — ... 3 Given that there is an efficient way to create the sequence classically, can we not just add a little check for whether we have encountered$x^{r} = 1 \ \text{mod} N$? During the creation process, it should not increase complexity to exponential-time, right? Why bother with quantum Fourier transform at all? Did I misunderstand it in some way? ... 3 This result concerns the black-box group model, which is a fairly standard model in computational group theory. It is intended to represent minimal assumptions on the groups we're working with. In the black box group model we assume that each group element has a (unique) string representation of a fixed length, and a black-box performs the group operations ... 2 "Hamiltonian Simulation" means applying the time evolution given by$H$to some initial state$|\psi\rangle$, i.e. to implement the unitary$U=e^{iHt}$on a quantum computer. If not mentioned otherwise, for an operator$H$,$\|H\|$generally denotes the operator norm, i.e., the largest eigenvalue (in absolute value) of$H$. Whether this is really the case ... 2 Sources on quantum computing tend to give a classical complexity of$\sqrt{2^n}$but not the proof. I believe the sources on classical cryptography call this algorithm birthday attack and use it to find collisions of hash functions (which is effectively what the Simon's algorithm does). You should be able to find the math details looking for it in crypto ... 2 First, note that for functions that do not change their value upon permutation of their inputs—or in other words, functions that only depend on the Hamming weight$|x|$of the input—it is known that the polynomial method tightly characterizes the query complexity, see Beals et al. In particular, this can be applied to the majority function$MAJ(x_1, \ldots, ...

2

The answer is yes to both questions. See page 2 of Bookatz's QMA-Complete Problems, which states: When a problem is given a unitary or quantum circuit, $U_x$, it is assumed that the problem is actually given a classical description $x$ of the corresponding quantum circuit, which consists of $\mathsf{poly}(|x|)$ elementary gates. Likewise, quantum ...

2

Speculatively expanding on previous answer Quantum computers tend to outperform classical computers in determining global properties of functions. Further, the properties tend to be some measure of global symmetry. Based on the global symmetry, the probability amplitudes can constructively (and destructively) interfere, in ways that a classical computer ...

2

Basic Definitions: If you don't know the definitions of the basic computational complexity classes well, I strongly recommend going through Watrous' lecture. We won't be using the quantum Turing machine formulation here, unlike the formal rigorous proof by Berstein and Vazirani. Anyway, I'm including a brief discussion on the definitions here. ...

2

The answer is no. The reason for this is the exponential size of the Hilbert space. Consider a single-tape TM with a matrix multiplication (MM) oracle which calculates the action of any unitary matrix on a vector of complex numbers. We'll define its input format as follows: $[U][x][\alpha_0 \ldots \alpha_{x-1}]$ where: $U$ is some symbol or series of ...

2

That really depends on the function $f$ and the size of $R\cdot T$. Generically, I don't think that you can expect improvements over $R\cdot T$, but improvements are possible in some special cases. For example, with the function $f$, there's a similar question in classical, and there are instances where speedups are possible, such as modular exponentiation: ...

2

Then I realized it is not just that; if we ever want to compute a superposition over some artificial objects, it is almost inevitable to get your superposition with some components being non-sense encoding. There must (or better be) some way to sanitize the input, right? But this is the point! We asume Merlin is powerful enough to prepare a uniform ...

1

It seems to me that the diagonalisation arguments that can be used are only slightly different from a standard one, e.g. such as can be found in these lecture notes about the Baker–Gill–Solovay Theorem (i.e., that there are oracles $A$ for which $\mathsf P^A = \mathsf{NP}^A$ and also oracles $A$ for which $\mathsf P^A \ne \mathsf{NP}^A$...

1

In essence you are asking could it be more efficient to use non-uniform distribution (instead of uniform) to pick numbers $r_i$ from $[0,S]$ for testing. Quantum circuit here just encodes the distribution, essentially it has no other use. Well, it depends on how we model our probability space for all polynomials. In some models it could be better to pick ...

1

I think you've simplified the problem too much. The way your question is framed it sounds like you expect a square-root speedup of a small problem, which doesn't seem that impressive. In actuality there may be a Grover-style speedup not of $O(\sqrt{X Y})$ but of $O(\sqrt{2^X 2^Y})$. Let's set up the problem, and see what is to be solved. Let's let your ...

1

As I understand $\mathsf{IP}$ and similarly $\mathsf{QIP}$, two parties, prover Peggy and verifier Vicky, engage in a number of rounds that are polynomial in $n$. Each round consists of Vicky providing a challenge to Peggy, then Peggy replying with a response, with the challenges and responses being a function of the previous rounds. Eventually after the ...

1

Initially I'll admit that I find the linked papers to be dense as well. However, to make some headway, a complete problem in $\mathrm{NP}$ can be phrased as "given a $\mathsf{3SAT}$ instance, does there exist a solution?" A complete problem in $\mathrm{coNP}$ is "given $\mathsf{3SAT}$ instance, do all inputs satisfy the $\mathsf{3SAT}$? Problems in the ...

Only top voted, non community-wiki answers of a minimum length are eligible