535 views

Asymptotically, Shor's algorithm is really efficient. Basically it's just: superposition, modular exponentiation (the slowest step), and a fourier transform. Modular exponentiation is what you do to ...

816 views

You just need to do a bit more algebra: Note that $$\sum_{i=0}^n (\overline{x_i+y_i})(x_i+y_i)=\langle x+y|x+y\rangle$$ and then you can distribute the right-hand side to get $$\langle x|x\rangle+\... View answer 1 answers 4 votes 247 views Accepted answer 6 votes A QFT can't arbitrarily raise the probability of any state you want to any value you want. Once you create a superposition, you need to find some way to make destructive interference occur between the ... View answer 1 answers 3 votes 74 views Accepted answer 5 votes Generally it's context-specific what the label means. For example, if x and y are integers, then if x\neq y then |x\rangle and |y\rangle are orthogonal (since they are different binary ... View answer 1 answers 4 votes 51 views 4 votes For surface codes, the syndrome measurements collapse the errors into either being X or Z errors. All Clifford gates have easy-to-compute commutation relations with X and Z gates. So the idea ... View answer 2 answers 4 votes 200 views 4 votes It depends on what you mean by an "actual quantum computer". For arithmetic circuits, and circuits to compute cryptographic operations to act as oracles for Shor's and Grover's algorithm, Toffoli ... View answer 2 answers 3 votes 238 views 4 votes I don't think that's possible: Suppose your initial state is \vert \phi\rangle. Let \vert \psi\rangle be a state with the numbers 1,4,8,13 in superposition. Then \langle \psi \vert \phi\rangle\... View answer 1 answers 7 votes 189 views Accepted answer 4 votes Grover focuses on gate costs, while Ambainis focuses on queries. Ambainis solves element distinctness in O(N^{2/3}) queries, using O(N^{2/3}) memory. If you used that memory to run O(N^{2/3}) ... View answer 2 answers 2 votes 254 views 3 votes The oracle for N\neq 2^n will be exactly the same, and the only difference is the diffusion operator. And in fact, all we need to change in the diffusion operator is the layer of Hadamard gates. ... View answer 1 answers 2 votes 52 views Accepted answer 3 votes As you point out, you have an \oplus of ket vectors, which isn't well-defined, so we will need to define this operation somehow. You definitely can't have \beta_0+\beta_1\mod 2 in a coefficient, ... View answer 2 answers 2 votes 145 views 3 votes Getting arbitrary superpositions can be done without too much difficulty if you have arbitrary single-qubit rotation gates. See here for several answers on how. Though, it might be easier to take ... View answer 1 answers 4 votes 164 views Accepted answer 3 votes This is the continued fraction part of the algorithm, step 5 on Wikipedia. What you've measured is y such that \frac{yr}{Q}\approx c, where c is some unknown integer, r is the hidden period (... View answer 1 answers 1 votes 77 views Accepted answer 3 votes Combining those two equations gives$$S(\rho')-S(\rho,\epsilon)\geq S(\rho)\geq S(\rho')-S(\rho,\epsilon)$$and since the left and right hand sides are the same, the inequalities must be equalities, ... View answer 1 answers 2 votes 55 views 2 votes There are lots of different ways. Generally, symmetric key cryptography has much less structure than asymmetric-key cryptography, so there usually isn't much benefit to looking for mathematical ... View answer 1 answers 2 votes 90 views Accepted answer 2 votes Grover's algorithm has two components, which alternate and repeat O(\sqrt{N}) times: a diffusion operator and an oracle operator. The diffusion operator will cause problems with your idea. As I ... View answer 1 answers 2 votes 58 views Accepted answer 2 votes Fermat's little theorem says that for a prime p, a^{p-1}\equiv 1\mod p for all a co-prime to p. This means the order of the group of powers of a will divide p-1, rather than p, hence why ... View answer 3 answers 3 votes 1k views 2 votes The linked question gives most of the relevant information but I want to focus on a few aspects of : My understanding is that, since we only need to iterate between all possible combinations of the ... View answer 2 answers 2 votes 187 views Accepted answer 2 votes Your intuition is correct, since rank-2 density matrices will be convex combinations of rank-1 density matrices, but they will be singular and hence will still be on the boundary. We can prove that ... View answer 1 answers 4 votes 120 views 2 votes Here's a silly method that works if you know y, you know the probability of measuring y, and you can efficiently generate arbitrary-size superpositions of the form$$\frac{1}{\sqrt{N}}\sum_{b <...

19 views

I'm mostly guessing, but I think it goes like this: We do a Grover search over row indices $i$. For the Grover oracle, on input $i$, we compute $A_iy$ and $z_i$ (where $A_i$ is the $i$th row of $A$). ...

54 views

I think the issue is that the total complexity of the modified oracle can be bounded. The total complexity will be (up to constant factors):  \sum_{j=0}^{t-1}\sqrt{\frac{N}{t-j}} = \sum_{i=1}^t \...

159 views

I'm going to change the notation slightly to make it a bit easier for me: I'll assume it's an arbitrary group of order $N$. There is a minor mistake in your first equation, which is that the QFT will ...

187 views
In this survey article they discuss Grover's algorithm. In my opinion, the most important part: Grover’s speed-up from $N$ to $\sqrt{N}$ is not as devastating as Shor’s speed-up. Furthermore, ...