Giuseppe Carleo May 23 2022 11:59 UTC

Several points of clarification are in order here:

1. We believe that referring to general computational complexity arguments to explain the intrinsic lack of scalability of a given algorithm only obfuscates the discussion and introduces further elements of confusion in the field.
The issue

...(continued)
Ryan Babbush May 20 2022 16:25 UTC

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

...(continued)
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

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

...(continued)
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

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

...(continued)
Arthur G. Rattew May 10 2022 03:57 UTC

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

...(continued)
Johannes Bausch May 09 2022 07:07 UTC

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)

...(continued)
John van de Wetering May 07 2022 22:54 UTC

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

...(continued)
Arthur G. Rattew May 05 2022 10:18 UTC

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

...(continued)
Craig Gidney May 04 2022 17:27 UTC

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

...(continued)
Arthur G. Rattew May 04 2022 11:17 UTC

Hello Craig,

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

...(continued)
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

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

...(continued)
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

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

...(continued)
Lorenzo Leone Apr 26 2022 15:44 UTC

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

...(continued)
Jon Tyson Apr 26 2022 07:27 UTC

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

...(continued)
Dominik Hangleiter Apr 20 2022 21:33 UTC

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 ...(continued) Robin Blume-Kohout Apr 13 2022 16:29 UTC *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 ...(continued) Shawn Geller Apr 05 2022 14:40 UTC Comments are welcome! Blake Stacey Apr 04 2022 02:23 UTC 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 ...(continued) 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 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 ...(continued) 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 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 ...(continued) Tom O Mar 20 2022 22:50 UTC 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 ...(continued) 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 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 ...(continued) 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 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 ...(continued) Nikolas Breuckmann Mar 01 2022 07:50 UTC 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 ...(continued) 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 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 ...(continued) 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 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 ...(continued) 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 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

...(continued)