Found it !

Line 2 should read EA X B instead of EA B.

Other than that my circuit looks identical to yours, I just used better variable names 😀.

The opcount is indeed 37. It turns out I had overcounted in a couple of places.

]]>I think I have a version that works now but with 41 operations instead of 37 and it’s a circuit instead of a formula. Now that I see how this works I’ll try to find the error in your slide.

]]>Sorry I meant to say Gaussian Elimination.

]]>I tried implementing the 4×4 matrix determinant formula from slide 7 of your wildidea.ppt presentation and it doesn’t seem to work when you substitute in numerical values. Maybe there was some information in the talk that isn’t in the slide. Obviously it assumes some pre-processing to avoid division by zero. I just ignore those cases when they occur but maybe there’s some additional pre-processing assumed that I’m not aware of ? Otherwise is there anything that explains where that formula comes from ? It’s not obvious to me how you get it from Gaussian Substitution.

]]>In terms of computational group theory, if we let \(H\) denote the Hadamard matrix (on one qubit) tensored with the identity (on \(n-1\) qubits), and if we let \(gen\) denote the set of all \(2^n \times 2^n\) permutation matrices together with \(H\), then \(gen\) finitely-generates a dense subgroup \(G\) of the orthogonal group (on \(n\) qubits). (The intuition is that oracles furnish the permutations, standard BQP methods furnish the \(H\) gate, and no other elementary gates are necessary for BQP universality.) The question then is about how rapidly this density is achieved, i.e. Does there exist an orthogonal matrix which is not well approximated by a ‘low height’ element of \(G\) i.e. not until a superpolynomially long string of generators is considered?

Counting (or rather upper-bounding) the number of points of \(G\) reachable within ‘\(k\) rounds’ of such gates, we see that there are \((2^n)!\) permutations available, so at most \((2^n)!^k\) points reachable after \(k\) rounds. Heuristically, the number of points of \(G\) reachable after polynomially many gates could be written \((2^n)!^{poly(n)}\), or \(2^{2^n \cdot n^{O(1)}}\). Perhaps standard results about epsilon nets in Lie algebras would be enough to resolve the question (albeit non-constructively) using these kind of counting arguments, though I’m not familiar enough with the methods to do this myself.

]]>(1) the Fourier component that you were looking for had a large enough magnitude, and

(2) your access to the function was of a kind that let you prepare the appropriate superposition state,

yes, you could. I think that, e.g., Sean Hallgren’s PhD thesis has material about the use of the QFT to learn about functions that aren’t fully periodic. ]]>

What if for some problem you could construct a function that was periodic but you needed to find not its period but whether it contained some specific frequency component. Would the QFT help with that ?

]]>In the core part of Shor’s algorithm, you’re given black-box access to a function that’s known to be periodic, and are asked to find its period. So, not only is there structure, there’s *abelian group structure*, which is the key thing that lets the Quantum Fourier Transform work. The periodicity structure makes the problem completely different from just searching for a needle in an exponentially large haystack, which is the problem addressed by Grover’s algorithm (for the latter, only a square-root speedup is possible). This is one of the most fundamental distinctions for anyone studying quantum algorithms.