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


6

There is always a difference between a quantum system and a classical metaphor. If a system is a qubit in a pure state, then there always exists a measurement basis (or alternatively a proper unitary gate for the standard measurement basis) such that the measurement outcome is 100% predictable, and a measurement basis with measurement outcome 50%-50%. You ...


6

Two quick comments before explaining this: The notes don't actually contain a proof of the claim made about the simulation; the intention was only to give a basic idea of how the simulation works. It is therefore not at all surprising that the mathematical justification is not clear, because the notes didn't even try to explain it. (It was the last lecture ...


6

Clearly $\mathrm{QMA \subseteq P^{QMA}}$, as we can construct a $\mathrm{P^{QMA}}$ algorithm to solve any problem in $\mathrm{QMA}$, by using an oracle call. The question is whether the reverse containment is known to hold. And the answer is that the reverse containment is not known to hold (and I think is not expected to hold). Of course, computational ...


4

Your metaphor can be chosen as $N-1$ identical coins, such that the outcome state vector corresponds to the sum of the heads. Thus we wind up in the state $|k\rangle$ when we have $k$ heads and $N-1-k$ tails. In this approach you can actually associate your metaphor with a classical phase space, as a generalization of the association of a qubit with the ...


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

We can think of the Rubik's cube Cayley graph $\Gamma=(V,E)$ with each (colored) edge $E$ being one of the Singmaster moves $\langle U,U^{2},U^{3}=U^{-1},D,D^{2},D^{3},\cdots\rangle$ and each vertex $V$ being one of the $43252003274489856000\approx 4.3e{19}$ different configurations of the $3\times 3\times 3$ cubes. The diameter of a graph is the longest ...


4

This question does not need to be phrased as a quantum question. One can equally ask what classical register can be used to store a string that uniquely identifies each different configuration of the Rubik’s Cube. This is already implicitly answered in the question: you need 27 bits, 14 trits.... However, this is labouring under the assumption that you can ...


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

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

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

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


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

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


2

A coin is not a great analogy for a quantum system. A (slightly) better one is a box that contains 3 coins. There are 3 windows, labelled x, y and z. The box is rigged so that you can only open one window at a time. When you open a window, you can see the heads/tails state of the corresponding coin, but the other two coins get flipped, and you can’t see what ...


2

A coin is an extremely bad and highly misleading analogy for a qubit. You shouldn't use it by any means. Yet, if you want an equally bad and misleading analogy for a qu-$d$-it, you should use something which is random and has $d$ possible outcome. For $d=3$, this might be rock-paper-scissors. On the other hand, a deck of cards with $52$ cards can have $...


2

Similar to Blue's picture, I like this one from Quanta Magazine better, since it seem to visually summarize what we are talking about.


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

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

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

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

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

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

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


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