Sam Jaques
  • Member for 3 years, 3 months
  • Last seen this week
3 answers
10 votes
535 views
Does Shor's algorithm end the search for factoring algorithms in the quantum world of computation?
Accepted answer
9 votes

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

View answer
1 answers
5 votes
816 views
Understanding a quantum algorithm to estimate inner products
Accepted answer
6 votes

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
Why do we use the quantum superposition for a period instead of factors in Shor's algorithm?
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
How should I understand the link between $x$ and $| x \rangle $?
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
Where does the "correction" in quantum error correction occur, specifically when using repetition codes?
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
Are Toffoli gates actually used in designing quantum circuits?
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
Finding the second smallest number. Is it achievable in QC?
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
How significant are the variants of Grover's Algorithm?
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
What is the circuit for grover's algorithm if N is not a power of 2?
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
Formulate Controlled-Not as mapping (including modulo-2 addition)
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
Is Grover's algorithm suitable for this search problem?
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
Shor's algorithm: what to do after reading the QFT's result twice?
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
Proof of quantum data processing inequality in N&C on pg 566
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
How would you apply quantum computing to break a symmetric key system?
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
Can I use Grover's algorithm on overlapping sets of qubits?
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
How to build an example of Shor's algorithm for the discrete log?
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
Is it possible to mine bitcoin by implementing Grover's algorithm on a quantum computer
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
Why is the boundary of the set of states in the generalised Bloch representation comprised of singular matrices?
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
Rewrite circuit with measurements with unitaries
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 <...

View answer
1 answers
2 votes
19 views
How to verify a matrix-vector product with Grover search?
1 votes

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

View answer
1 answers
2 votes
54 views
Grover search with multiple solution implementation strategy
1 votes

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

View answer
2 answers
2 votes
159 views
Shor's Discrete Logarithm Algorithm with a QFT with a small prime base
1 votes

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

View answer
1 answers
2 votes
187 views
How does the Grover's Algorithm work with a real example?
1 votes

In your card example, since you've created the encoding, you've kind of already made Grover's algorithm useless. That is, you already know that 00 is the spade of Ace, so you don't need to search. ...

View answer
1 answers
2 votes
338 views
Consequences of Grover's algorithm
Accepted answer
1 votes

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

View answer