Exponential challenges in unbiasing quantum Monte Carlo algorithms with q...

Giuseppe Carleo May 23 2022 11:59 UTCRyan Babbush May 20 2022 16:25 UTC

...(continued)The challenge referred to in this paper was first identified and discussed extensively in the original text by Huggins et al. - see, e.g., Appendix F. Although there are some differences, the problem is similar in spirit to the vanishing of initial state overlaps when preparing ground states via qua

Sevag Gharibian May 20 2022 15:12 UTC

Minor typo - de Beaudrap is spelled wrong in your abstract! Thanks for posting!

Jon Tyson May 19 2022 14:34 UTC

A previous construction of so-called "dual unitaries" from biunimodular functions appeared in

https://arxiv.org/abs/quant-ph/0306144. (See Theorem 7 and the discussion in section 4.)

Arthur G. Rattew May 17 2022 08:08 UTC

...(continued)Hi Johannes,

Sorry for the delay in responding -- this has been a busy period for both BΓ‘lint and myself.

We appreciate your input, and will certainly address these points comprehensively in an updated version of the paper.

Additionally, we will reach out to you to ensure that our comment

Alex Meiburg May 16 2022 17:37 UTC

The approach of Jerrum/Sinclair/Vigoda is restricted to matrices with non-nonnegative entries. My understanding is that this is viewed as an "essentially easy" case, no? Joonsuk Huh's algorithm would be more exciting to apply to matrices that include negative entries?

Ryan Babbush May 11 2022 21:11 UTC

The claim made in the final sentence of this abstract is not substantiated by any available evidence. This sort of hype is detrimental to the quantum computing field and should be called out, especially when it is difficult to believe such claims are made in good faith.

Johannes Bausch May 11 2022 07:28 UTC

...(continued)Thanks a lot for your quick answer!

Regarding the normal distribution, I think there is a difference in the meaning of $N=2^n$ in our papers; for you it appears to be the resolution over a fixed domain (if I'm not mistaken?), whereas in 2009.10709 it is an absolute coordinate. This means that in

Arthur G. Rattew May 10 2022 03:57 UTC

...(continued)Dear Johannes,

Thank you for your comment. The black-box state preparation techniques you have referenced are quite interesting and will certainly be useful in practice!

In the following, we assume that $n$ is the number of qubits, and $N = 2^n$ is the resolution.

First, our query complexi

Johannes Bausch May 09 2022 07:07 UTC

...(continued)Dear Arthur, dear Balint,

Really interesting paper, thanks! As Craig I have a question regarding your technique's efficient, namely in comparison to known black box state preparation tasks, for instance 1807.03206, 2009.10709, and more recently 2105.06230. (1) and (2) are of the same nature; (3)

John van de Wetering May 07 2022 22:54 UTC

...(continued)In https://dl.acm.org/doi/10.1145/1008731.1008738 it is shown how to classically approximate within polynomial time the permanent up to some given error epsilon. The trick there is that the time dependence is on poly(1/epsilon). If the time dependence is poly(log(1/epislon)) then the problem becomes

Arthur G. Rattew May 05 2022 10:18 UTC

...(continued)We refer to the algorithm as *quasi-deterministic* because (for analytical convenience) we only proved our error-bound using a single outcome of the measurement of the ancillary register (which happens asymptotically with probability 1), and assumed that we rejected all other outcomes. However, in p

Craig Gidney May 04 2022 17:27 UTC

...(continued)Ah, the deterministic aspect is important in some chemistry algorithms based on PREP+SELECT oracles. PREP is a bit poorly named because it has to run in contexts where its input is not all reset qubits, in order to maintain coherence during amplitude amplification. You would want to have very good c

Arthur G. Rattew May 04 2022 11:17 UTC

...(continued)Hello Craig,

Thank you for your question.

While rejection sampling adds an ancillary qubit to an initial state and applies conditional single-qubit rotations to it (such that after measuring out the ancilla qubit the desired state is obtained with some probability), we go all the way and devi

Craig Gidney May 03 2022 08:08 UTC

What are the advantages of this method over rejection sampling, which also scales inversely in the filling ratio and requires one call to the oracle per attempt?

Victory Omole May 02 2022 18:18 UTC

Ah, that makes sense. Thank you for the detailed answer. I will try Qermit out!

Dan Mills Apr 28 2022 08:49 UTC

...(continued)Hi Victory, many thanks for your message! Mitiq is great, and you're quite right that it breaks down the implementations of each protocol. In the case of Mitiq this could be seen as a result of the attentive development of the software. In the case of Qermit this breakdown of protocols into submodul

Dominik Hangleiter Apr 26 2022 18:07 UTC

Thanks, Lorenzo, for your reply. That makes sense, and I fully agree with everything you say :).

Maybe it's worth to stress that point then: your result applies to *families of states* that are defined by their amount of magic rather than individual states, correct?

Victory Omole Apr 26 2022 15:58 UTC

...(continued)Thanks for this package! The paper says

> Qermit is complementary to Mitiq [23], which is an opensource Python toolkit that implements an overlapping set of error mitigation schemes. Qermit takes a different approach that

breaks-down the implementation of each protocol into standalone modular un

Lorenzo Leone Apr 26 2022 15:44 UTC

...(continued)Dear Dominik, happy to hear from you. We are sorry for the late response.

The answer is yes and no. From the one hand, what you say is true. You can perform direct fidelity estimation on the state $(U_{1}\otimes\ldots U_{n})|\psi\rangle $ by expanding the fidelity between the theoretical state an

Jon Tyson Apr 26 2022 07:27 UTC

...(continued)What is referred to as "dual unitaries" was previously called "maximally entangled unitaries" in https://arxiv.org/abs/quant-ph/0306144, and more such operators were constructed there from biunimodular functions. They are maximally entangled in the sense of Mike Nielsen's operator schmidt decomposi

Dominik Hangleiter Apr 20 2022 21:33 UTC

...(continued)Hi Lorenzo, Salvatore and Alioscia,

consider an $n$-qubit stabilizer state $| \psi \rangle$ with stabilizers $S_1,\ldots, S_n$. Then the state $U | \psi \rangle$ with $U = U_1 \otimes \cdots \otimes U_n$ for *arbitrary* single qubit unitaries $U_1, \ldots, U_n$ is stabilized by $U S_1 U^\dagger

Robin Blume-Kohout Apr 13 2022 16:29 UTC

...(continued)*I've removed the text of this comment, because it addressed a prior comment that has since been deleted. Absent the prior comment, there is no need for my words to appear here. However, I've chosen not to delete the comment entirely in order to leave a record that there was once a discussion here

Shawn Geller Apr 05 2022 14:40 UTC

Comments are welcome!

Blake Stacey Apr 04 2022 02:23 UTC

...(continued)This is an interesting development!

Up until this point, it has seemed to me that while the RQM literature endorsed up front a strong form of relationalism, when one dug into the details, the writing backed away from it. For example, measurement outcomes were treated as relative to an observer, b

Tom O Mar 30 2022 14:59 UTC

Hey Hong-Ye, yes thank you for the reply!

Hsin-Yuan Huang Mar 26 2022 17:46 UTC

Hi Jerome,

Thank you so much for the additional references! We will include these works in the next update.

Best regards,

Robert (Hsin-Yuan Huang)

Jerome Gonthier Mar 24 2022 13:14 UTC

...(continued)Very interesting! Regarding Section III.G about variational quantum-classical algorithms, it could be worth mentioning grouping methods that are not directly related to randomized measurements. Indeed, these methods seem to outperform classical shadow methods in several examples. See Fig. 3 in http

Alex Meiburg Mar 23 2022 20:53 UTC

I enjoyed this paper! One question, on equation (3) and the immediately preceding definition of P_n(U), is the a_n supposed to be a_{n+1}?

Hong-Ye Hu Mar 21 2022 19:10 UTC

...(continued)Hi Tom, thanks for your interest. In the second case you mentioned, it is still a $[[N=nk,k]]$ error correction code.

If one uses global Clifford group for shadow tomography, the sample complexity for predicting O scales as the rank of operator, here it would be P*O, where P is the projection op

Tom O Mar 20 2022 22:50 UTC

...(continued)Really nice! One thing I'm not sure about after reading is whether the $k$ in the $4^k$ in the bound for sample complexity refers to either:

1. the $k$ in the stabiliser code definition i.e. $[n,k]$ indicates you can encode $k$ logical qubits in $n$ physical qubits.

2. The total number of logi

Kaelan Donatella Mar 11 2022 09:45 UTC

Hi,

I found your work quite interesting and original in the way you change the storage of an operator. Maybe you would be interested in this somewhat similar work, that also works for weakly dissipative bosonic systems https://arxiv.org/abs/2102.04265 (see appendix I.5 and figure 6)

Best

Sevag Gharibian Mar 04 2022 17:44 UTC

This was an important conversation to start, thank you for doing it.

Robin Blume-Kohout Mar 03 2022 12:27 UTC

...(continued)This looks like a nice result, but it might be worth referencing the main result of "[Efficient Method for Computing the Maximum-Likelihood Quantum State from Measurements with Additive Gaussian Noise][1]" (PRL 108, 070502 (2012)). It seems closely related, albeit focused on removing the negative p

Nikolas Breuckmann Mar 03 2022 10:33 UTC

Hey Anthony, no worries! The connection is not obvious and we do not mention local testability in our paper.

Anthony Leverrier Mar 01 2022 07:57 UTC

...(continued)Hi Niko.

Really sorry for that! We cited your paper when we mentioned recent constructions of good quantum LDPC codes, but it's completely true that we should have mentioned that your balanced product codes were also giving the codes of Dinur et al. We'll acknowledge that in a revision of the paper

Nikolas Breuckmann Mar 01 2022 07:50 UTC

...(continued)I do not want to be *that guy*, but I would like to point out that the codes of Dinur et al. are the balanced product codes we conjectured to be good LDPC quantum codes in https://arxiv.org/abs/2012.09271 .

Dinur et al. point this out in a revised version of their paper https://arxiv.org/abs/2111.0

Aram Harrow Feb 22 2022 22:02 UTC

Daochen Wang pointed out that Lemma 4.3 is false. In fact, discarding registers 1 and 2 yields a mixture of |z(f(a))> for uniformly random $a\in A$

Jahan Claes Feb 22 2022 04:33 UTC

...(continued)Interesting work! I was under the impression that any imaginary time evolution algorithm had to fail for some local Hamiltonians, as finding the ground state of gapped local Hamiltonians is NP complete. If you try to do the imaginary time evolution with LCU, you could see the success probability of

Henry Yuen Jan 29 2022 00:20 UTC

I also would like to point out that Gregory Rosenthal also has a paper from November that shows how to construct arbitrary n-qubit states in depth O(n) with exponentially many ancillas. (https://arxiv.org/pdf/2111.07992.pdf).

Guojing Tian Jan 28 2022 14:54 UTC

The result of this Theorem 1 was actually a special case of a more general result in arXiv:2108.06150v2 in November of last year, where the authors showed how to achieve the optimal depth for an anbitrary number of ancillary qubits, among other results.

Filip Maciejewski Jan 28 2022 13:56 UTC

Indeed, that's what Theorem 1 states:

Theorem 1 (Arbitrary quantum state preparation). With only

single- and two-qubit gates, an arbitrary π-qubit quantum state

can be deterministically prepared with a circuit depth Ξ(π)

and π(π) ancillary qubits.where N = 2^n.

Aram Harrow Jan 28 2022 13:11 UTC

I haven't read the paper but the abstract says they use ancilla, presumably exponentially many in the worst case.

Martin Kliesch Jan 28 2022 10:25 UTC

Arbitrary quantum states cannot be prepared with poly sized quantum circuits in the sense of https://arxiv.org/abs/1102.1360. How is this compatible with these results?

Blake Stacey Jan 24 2022 20:05 UTC

...(continued)Parikh and Verlinde's "De Sitter Holography with a Finite Number of States" is cited three times in the bibliography (references 38, 39 and 40 are isomorphic). In addition, reference 45 replicates reference 44.

Apropos: Does anyone know the *first* time that the Bekenstein bound was reinterpreted

Michal Oszmaniec Jan 21 2022 09:44 UTC

Thanks for clarification David! In my thinking I was "fixated" on density matrices and channels and it was harder to see this.

Craig Gidney Jan 21 2022 05:58 UTC

I have been wondering about this 2018 ( https://quantumcomputing.stackexchange.com/q/4912/119 ) and finally someone did it.

Raz Firanko Jan 20 2022 14:01 UTC

Hi, nice results!

You a small typo on your proof of Theorem 17:

To minimize over P.S.D operators you need to switch to

$A=\rho^{1/4}B\rho^{1/4}$ and not $A=\rho^{1/2}B$ which is generally not positive.

Alex Meiburg Jan 19 2022 18:57 UTC

Is the Appendix currently available anywhere? :)

David Gosset Jan 19 2022 14:04 UTC

...(continued)Thanks, Michal! To answer your question, say we are interested in the marginal probability for obtaining $x\in \{0,1\}^{|A|}$ when measuring a subset $A\subseteq [n]$ of the qubits in the computational basis, starting from a state $U|0^n\rangle$ where $U$ is a depth-$d$ circuit. We can write this m