——————–

Of course, you could also “instantiate” Fourier Fishing with an explicit Boolean function. If you do that, then you get something that’s basically equivalent to Bremner, Jozsa, and Shepherd’s IQP model. For that model, we have results about the hardness of exact sampling directly analogous to what we have for BosonSampling (i.e., if you can do it efficiently classically, then PH collapses to BPP^{NP}). But we don’t yet have results about the hardness of approximate sampling analogous even to the incomplete results that we have for BosonSampling.

In the slides, you refer to your 2009 result about Fourier Checking. I’m wondering what your current take is on the other result in that paper, about Fourier Fishing.

My interpretation of Fourier Fishing has always been that you give a black box problem that’s solvable in polynomial time on a quantum computer; whereas that black box problem is not in the classical polynomial hierarchy (that is, a reasonably natural definition of PH for black box problems).

To me, it seems like a pretty strong result. But, in conversations over the years, I’ve often found myself defending the interestingness of it.

If you had included it in your talk, what would you have said?

]]>http://arstechnica.com/staff/2014/10/harnessing-depression-one-ars-writers-journey/

]]>quantum states that are more abstract than superposition of

electrons only 0/1 possible assume i superpose wavelength l1 with l2

what will be the size of such a quantum register will it still be a

qbit or is it a qDigit ? even if we can somehow implement a qDigit

what quantum operators can we define on it ? ]]>

There’s some magic about constant factors in the classical case. These days we use DRAM, which is a brilliant invention of an electronic circuit that lets you store lots of bits in both very little circuit board space and much less energy consumption than the more obvious SRAM. But of course, as while we have no idea how to build practical quantum computers at all currently, we can’t really speculate about the details in quantum computers.

]]>Now I think I understand your beamsplitter network example: the n beamsplitters somehow act to encode the N-dim vector, so that when a photon passes through, the photon is in the state |psi>, which took O(1) effort (time for the photon to pass through the beamsplitter network).

Is there any physical-implementation-agnostic way to describe how to construct a qRAM? Can we describe the construction and operation of a qRAM in terms of qubits and one- and two-qubit gates? (Of the small number of papers I’ve seen in the literature so far, they all seem to give examples of how to construct a qRAM using some very specific set of physical tools, e.g. optical beamsplitter networks; atoms in cavities and photons, etc.)

In the case of the beamsplitter network qRAM you describe, what is the physical meaning of the qubits in the resulting |psi>? e.g., for n=3, I first thought that |100> is the state where there is 1 photon in the first mode, and 0 photons in the second and third modes. However, I suppose that’s not right, since then if you only put a single photon into the beamsplitter network, only the states |100>, |010> and |001> can have non-zero amplitude (and |000> if you consider photon loss). Let’s suppose I want to make a beamsplitter qRAM that can produce the following |psi>, how would I do it?

|psi>=(1|000> + 1.1|001> + 1.2|010> + 1.3|011> + 1.4|100> + 1.5|101> + 1.6|110> + 1.7|111>)/a

(where “a” is the normalization factor)

Thanks again, and good luck with the article. If you have even some of your discussion points from this comment thread in it, I think it’s going to be a really helpful article.

]]>For graph isomorphism, it’s true that we don’t know a distribution over hard instances, but at least it’s very easy to state the problem being solved. Whereas with HHL, the problem being solved is often summarized as “solving linear systems,” but of course there are 3 caveats (how to specify the input, the condition number, what observable to measure about the solution vector). As long as those caveats are remembered, I’d say yes, it’s very similar to graph isomorphism.

]]>