Pith. sign in

REVIEW 4 major objections 5 minor 48 references

Quantum algorithm for estimating Renyi entropies of quantum states

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A quantum algorithm estimates Rényi entropies of unknown states using one-clean-qubit trace estimation and block encodings, with measurement counts that can beat copy-based sample complexity.

desk verdict The main complexity claim overlooks a dimension-dependent DQC1 normalization factor, so the advertised O(1/(xε)^2) bound does not hold; the QSVT+DQC1 idea is still worth a serious referee. read the letter →

arxiv 1908.05251 v2 pith:UHF4KAG6 submitted 2019-08-14 quant-ph

Sathyawageeswar Subramanian , Min-Hsiu Hsieh This is my paper · ORCID
classification quant-ph MSC 81P6868Q12
keywords RényientropyquantumsingularvaluetransformationsblockencodingsDQC1one-clean-qubitmodeltraceestimationpurifiedqueryaccessmultiplicativeapproximationcomplexity
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proposes a quantum algorithm to estimate the $\alpha$-Rényi entropy $S_\alpha(\rho)=\frac{1}{1-\alpha}\log\mathrm{Tr}(\rho^\alpha)$ of an unknown density matrix, under the purified quantum query access model: access is given to a unitary that prepares a purification of $\rho$. The main claim is that an additive-$\epsilon$ estimate can be obtained with an expected $O(1/(x\epsilon)^2)$ independent runs of a circuit that measures a single qubit and invokes the purification oracle $O(\frac{1}{\delta}\log(d/\epsilon))$ times, where $x=\frac{1}{d}\mathrm{Tr}(\rho^\alpha)$ and $\delta$ is a lower bound on the smallest eigenvalue. This is a different resource profile from the $\Theta(d^2/\epsilon^2)$ copies needed in the standard independent-copies model, and it avoids amplitude estimation, replacing deep circuits with many shallow measurements. The same iterative routine also yields multiplicative approximations to the entropy with overhead that is at most logarithmic in the dimension.

What carries the argument

The load-bearing mechanism is the combination of block encodings with one-clean-qubit trace estimation. A block encoding is a unitary whose top-left block is a rescaled copy of the matrix of interest; quantum singular value transformations convert the purification oracle into an $\epsilon$-approximate block encoding $U_\alpha$ of $\rho^\alpha$, with the transformation cost controlled by $\delta$ and $\alpha$. The DQC1 circuit then obtains the normalized trace of $U_\alpha$ by reading the Pauli expectation values of a single clean qubit, and a conditional-phase trick isolates the real trace contribution of the $\rho^\alpha$ submatrix. The identity doing the work is $S_\alpha(\rho)=\frac{1}{1-\alpha}\log x$ with $x=\frac{1}{d}\mathrm{Tr}(\rho^\alpha)$: a multiplicative estimate of $x$ becomes an additive estimate of $S_\alpha$, and the iterative routine of [25] achieves that multiplicative precision with expected cost $O(1/(x\epsilon)^2)$.

What would settle it

Construct the full block-encoding unitary from Lemma 4 for a purification with $a$ ancilla qubits and compare the exact normalized trace of its top-left block with $\mathrm{Tr}(\rho^\alpha)/2^{a+2s}$; if the rescaling factor is not constant in $a$, then simulating the paper's prescribed measurement schedule on a state with known spectrum will show the error exceeding $\epsilon$ at the claimed number of measurements.

Watch

Extended reading notes

Core claim

The central claim is that Rényi entropies can be estimated from a purification oracle using only shallow circuits and many single-qubit measurements. The algorithm first builds a block encoding of $\rho^\alpha$ from the purification oracle via quantum singular value transformations, then estimates the normalized trace of that block-encoding unitary in the one-clean-qubit (DQC1) model, and finally feeds the result into an iterative routine that upgrades additive estimates to multiplicative ones. Theorem 1 states that for $\alpha>0$, $\alpha\ne 1$, and $\delta I \preceq \rho \preceq I$, the procedure outputs $\tilde S$ with $|\tilde S-S_\alpha(\rho)|\le \epsilon$ with high probability, using an expected $O(1/(x\epsilon)^2)$ single-qubit measurements, each on a circuit that invokes the oracle $m=O(\frac{1}{\delta}\log(d/\epsilon))$ times; when $\alpha$ is an integer, $m=\alpha$ and the circuit depth is independent of $d$. Theorem 2 iterates this to give a multiplicative approximation $(1-\epsilon_{\rm rel})S_\alpha \le \hat S \le (1+\epsilon_{\rm rel})S_\alpha$ in $R=O(\log(\log d/\delta))$ rounds. The paper also notes that when $\alpha<1$, the block encoding can be pre-amplified by a factor $d$, making any additive estimate effectively multiplicative.

Load-bearing premise

The measurement-count bound assumes that the normalization factor between the one-clean-qubit circuit's estimate and the true value of $\mathrm{Tr}(\rho^\alpha)$ is independent of the dimension $d$; the paper does not analyze how the purification ancilla dimension contributes to that factor, so the stated $O(1/(x\epsilon)^2)$ count stands only if that factor is truly $d$-independent.

Editorial extensions

If this is right

  • With purified access, estimating the $\alpha$-Rényi entropy has measurement cost $O(1/(x\epsilon)^2)$ instead of the $\Theta(d^2/\epsilon^2)$ samples needed in the independent-copies model, so for large $d$ the saving can be substantial when $x$ is not too small.
  • For integer $\alpha$, each circuit uses exactly $\alpha$ oracle calls, so the circuit depth does not grow with the dimension $d$, at the price of a large number of repetitions.
  • Multiplicative approximations to the entropy are obtained by iterating the additive procedure, with at most $O(\log(\log d/\delta))$ rounds, a regime not previously covered in the quantum algorithm literature.
  • The scheme needs only one clean qubit while the rest can be maximally mixed, making the resource requirements compatible with near-term NMR or linear-optics experiments rather than full fault-tolerant hardware.
  • For $\alpha<1$, pre-amplifying the block encoding by $d$ makes any additive trace estimate effectively multiplicative, bringing the measurement cost down to $O(1/\epsilon^2)$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension not stated in the paper is to replace the monomial $\rho^\alpha$ with other smooth matrix functions $f(\rho)$; the same block-encoding-plus-DQC1 pipeline would estimate $\mathrm{Tr}(f(\rho))$ whenever quantum singular value transformations can implement a polynomial approximation of $f$.
  • The advantage over copy-based sample complexity is tied to the purified oracle model; for states provided only as repeated copies, the $\Theta(d^2/\epsilon^2)$ sample bound remains the relevant benchmark, so the algorithm's benefit depends on whether the preparation unitary is actually available.
  • The unanalyzed normalization factor connecting the DQC1 output to $\mathrm{Tr}(\rho^\alpha)$ is a gap that explicit computation could close; if the factor depends on $d$, the claimed measurement count would degrade and the comparison to the sample-complexity model would need revisiting.
  • A small-scale implementation on a known few-qubit state could map the constant factors in $O(1/(x\epsilon)^2)$ and clarify when the shallow-circuit/many-measurements tradeoff actually beats amplitude estimation.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

Summary. The paper proposes a quantum algorithm for estimating the α-Rényi entropy of an unknown d-dimensional density matrix in the purified quantum query access model. The method combines block encodings of ρ^α obtained via quantum singular value transformations with DQC1 normalized-trace estimation, and uses an iterative procedure of Chowdhury et al. to convert additive trace estimates into multiplicative ones. The central claim, Theorem 1, is that for α>0, α≠1, an additive ε-approximation to S_α(ρ) can be obtained with high probability using an expected O(1/(xε)^2) independent applications of a circuit that queries the purification oracle U_ρ and U_ρ^† O((1/δ)log(d/ε)) times, with a single qubit measurement per run, where x=(1/d)Tr(ρ^α). Theorem 2 extends this to multiplicative precision with an additional logarithmic-in-d overhead. The paper compares this favorably with the Θ(d^2/ε^2) sample complexity of copy-based estimation.

Significance. If the central complexity bound were correct, the paper would make a useful conceptual contribution: it would show that in a purified-oracle model, Rényi entropies can be estimated using shallow circuits and many single-qubit measurements, without the long coherent control required by quantum amplitude estimation. The combination of QSVT block encodings with DQC1 trace estimation is natural and not, to my knowledge, previously explored, and the use of the iterative expected-runtime analysis of Chowdhury et al. is a genuine attempt to go beyond worst-case bounds. The paper is also honest about its limitations, noting that the decision version of entropy estimation is not placed in DQC1. However, the main theorem's measurement bound is not supported: the DQC1 normalized trace of the constructed block-encoding unitary is scaled by a d-dependent factor that the manuscript treats as constant. This invalidates the advertised comparison with Θ(d^2/ε^2) and, as stated, the algorithm does not achieve the claimed improvement.

major comments (4)
  1. [Section IV.B and Theorem 1] The central complexity claim is not supported because the DQC1 measurement does not estimate x=(1/d)Tr(ρ^α) up to a d-independent constant factor. By Lemma 4, the block encoding of ρ acts on a+2s qubits, where s=log d and a is the purification ancilla size; after Lemma 6, the unitary U_α acts on n=a+2s+2 qubits, so DQC1 returns Tr(U_α)/2^n with 2^n=4·2^a d^2. The ρ^α block contributes Tr(ρ^α)/2^n = x/(4·2^a d) to this normalized trace. The sentence in Section IV.B that a multiplicative approximation is unaffected when the estimate is scaled by a constant treats 4·2^a d as a constant, but this factor depends on d and on a; since δI ≼ ρ implies ρ is full rank, any purification requires 2^a ≥ d. Therefore the number of DQC1 runs needed to estimate x to relative error γ is O((2^a d/(γ x))^2) = Ω(d^4/(γ^2 x^2)), not O(1/(γ x)^2). This invalidates Theorem 1 as stated, and Theorem 2 and Equation (13) inherit the same missing factor.
  2. [Section IV.B] The subtraction trick with the controlled-phase unitary V does not repair the normalization problem. Both Re(Tr(U_α)) and Re(Tr(U_α′)) are normalized by the same denominator 2^n, so the difference estimates the normalized block contribution Tr(ρ^α)/2^n, not Tr(ρ^α). The statement that an estimate of (1/d)Tr(ρ^α) to multiplicative precision is also a valid estimate of Tr(ρ^α) to the same precision conflates the normalized and unnormalized traces and ignores the dimension-dependent factor 2^n/d.
  3. [Appendix B] The stopping-time analysis contains a reversed inequality. With q defined by x_max/2^{q−1} > x > x_max/2^q, for r ≥ q+1 one has x_r = x_max/2^r < x, whereas the text states that r ≥ q+1 implies x_r > x. Consequently the claimed bound Pr(˜x_r < x_r) ≤ 1−c′ does not follow from the stated premise. In addition, the comment in Algorithm B.1 that AdditiveEstimate returns ˜x_r with Pr(|x_r−˜x_r| < ε_r) > c′ is incorrect as written, since the subroutine estimates the unknown quantity x, not the known threshold x_r. The expected-measurement formula (B4) may be salvageable with a corrected argument, but the proof given in the manuscript is not valid as it stands.
  4. [Section IV.C] The parenthetical proposal for α<1, which claims that scaling up the block encoding of ρ^α by d using pre-amplification makes 'the normalized trace larger than unity,' is not correct: a normalized trace of a unitary cannot exceed unity, and Lemma 7 amplifies eigenvalues only while they remain below 1, so it cannot be used to multiply the block by d when the resulting operator norm exceeds 1. As written, this passage does not provide a valid alternative complexity bound.
minor comments (5)
  1. [Theorem 1] The notation C^{d+a} for the input unitary is ambiguous: it is not clear whether a is an ancilla dimension or a number of ancilla qubits, and the total dimension of the block-encoding unitary U_α is never stated explicitly. The construction in Lemma 4 implies U_α acts on 2^{a+2s+2} dimensions, which should be stated in the theorem.
  2. [Section IV.B] The phrase 'normalised trace of this d+a-dimensional unitary U_α' is inconsistent with the block-encoding construction, which acts on a+2s+2 qubits; the dimension should be written as 2^{a+2s+2}.
  3. [Algorithm B.1] The comment inside Algorithm B.1 defining the additive estimate should read Pr(|x−˜x_r| < ε_r) > c′, not Pr(|x_r−˜x_r| < ε_r) > c′; as printed, the condition refers to the known quantity x_r and is not meaningful.
  4. [Table I] The column 'E[#mmts]' in Table I omits the dimension-dependent normalization factor identified in the major comments; if the corrected bound is used, the comparison with the sample-complexity results of [19] must be revisited.
  5. [Section IV.C] The sentence about the α<1 case and pre-amplification should be rewritten or removed, since it appears to claim that a normalized trace can exceed unity and is not supported by the cited lemma.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation composes external QSVT and DQC1 results with an independent iterative estimator; the only author-overlap citation is non-load-bearing.

full rationale

The paper's central derivation is self-contained in the relevant sense. Theorem 1 combines (i) Lemma 4 and Lemma 6 of Gilyén et al. [27] to convert the purified oracle Uρ into a block encoding of ρ and then into an approximate block encoding of ρ^α; (ii) the standard DQC1 normalized-trace estimation circuit; and (iii) the iterative additive-to-multiplicative estimator of Chowdhury et al. [25]. The relation between the estimated x=(1/d)Tr(ρ^α) and the Rényi entropy is just the definition Sα=(1/(1-α))log Tr(ρ^α), so the error propagation in Section IV.A is definitional in a legitimate sense, not a circular import of the conclusion. The measurement-complexity bound O(1/(xε)^2) is an expected-runtime analysis of the external iterative procedure applied to additive trace estimates; it is not obtained by fitting parameters to the target quantity. The only author-overlap citation is [34] (Subramanian, Brierley, Jozsa), invoked as one option for exact monomial implementation for integer α; the paper also cites [27] for the general ε-approximate power construction, so [34] is not load-bearing. The skeptic's concern about the normalized-trace denominator N=4·2^a d^2 is a technical scaling/correctness issue about whether the rescaled factor is constant, not a circular reduction: the algorithm would still estimate the same trace quantity, just with a different (possibly d-dependent) normalization. No fitted input is relabeled as a prediction, no uniqueness claim is imported from authors' prior work, and no known result is merely renamed.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper's central claim rests on standard QSVT results, the DQC1 model, the non-singular input assumption, and the iterative estimator from [25]. There are no fitted numerical parameters. The main unexamined burden is the trace-normalization factor connecting the DQC1 normalized trace to x.

assumptions (5)
  • standard math The QSVT and block-encoding lemmas of [26,27] correctly produce an ε-approximate block encoding of ρ^α with query complexity O(max(1,α)/δ log(1/ε)).
    Used in Section IV B and Appendix A; the paper quotes these as black boxes without reproving them.
  • standard math Lemma 4 of [27] converts the purified oracle Uρ into an exact block encoding of ρ with the stated ancilla count.
    This is the entry point for constructing Uα; the dimension of this encoding is central to the DQC1 normalization issue.
  • standard math The iterative estimator of Chowdhury et al. [25] (Algorithm B.1) produces a multiplicative estimate with high probability and expected number of additive calls O(1/(x ε_rel)^2).
    The paper relies on this for both Theorem 1 and Theorem 2; the partial analysis in Appendix B contains a reversed-inequality issue.
  • domain assumption The input state is non-singular with minimum eigenvalue at least δ>0, known to the algorithm, and the trace x = (1/d)Tr(ρ^α) is nonzero.
    Assumed in Theorem 1 and Lemma 6; non-integer powers of ρ are handled only on [δ,1], and multiplicative entropy estimation fails for pure states with zero entropy.
  • ad hoc to paper The DQC1 measurement of the full block-encoding unitary can be converted to an estimate of the submatrix trace Tr(ρ^α)/2^s with only a constant multiplicative error factor.
    This is the fragile step: the phase method in Section IV B cancels the bottom-right block, but the trace is still normalized by the full unitary dimension, and the paper does not bound that dimension or the resulting rescaling factor.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Quantum algorithm for estimating Renyi entropies of quantum states." pith.science (2026). https://pith.science/paper/UHF4KAG6

@misc{pith2026190805251,
  author       = {Pith},
  title        = {Pith review of: Quantum algorithm for estimating Renyi entropies of quantum states},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/UHF4KAG6}},
  note         = {Machine review of arXiv:1908.05251}
}
abstract

We describe a quantum algorithm to estimate the $\alpha$-Renyi entropy of an unknown density matrix $\rho\in\mathcal{C}^{d\times d}$ for $\alpha\neq 1$ by combining the recent technique of quantum singular value transformations with the method of estimating normalised traces in the one clean qubit model. We consider an oracular input model where the input state is prepared via a quantum oracle that outputs a purified version of the state, assumed to be non-singular. Our method outputs an estimate of the $\alpha$-Renyi entropy to additive precision $\epsilon$, using an expected total number $O\left(\frac{1}{(x\epsilon)^2}\right)$ of independent applications of a quantum circuit which coherently queries the input unitary $O\left(\frac{1}{\delta}\log \frac{d}{\epsilon}\right)$ times, in each case measuring a single output qubit. Here $\delta$ is a lower cutoff on the smallest eigenvalue of $\rho$ and $x=\frac{1}{d}\!\mathop{Tr}{\rho^\alpha}$. The expected number of measurements made in this method can be compared to results in the sample complexity model that generally require $\Theta(d^2/\epsilon^2)$ samples. Furthermore, we also show that multiplicative approximations can be obtained by iteratively using additive approximations, with an overhead logarithmic in the dimension $d$.

Figures

Figures reproduced from arXiv: 1908.05251 by the authors.

Figure 1
Figure 1. A DQC1 circuit that can be used to estimate 1/2 n Tr (U), for which no classical efficient algorithm is known. Measurements are made in the computational basis. The initial state consists of one qubit set to the |0i state, and n qubits in the maximally mixed state, i.e. ξin = |0ih0| ⊗ 1n/2 n = 1+Z 2 ⊗ 1n/2 n. We can write the final state in figure 1 after the application of the circuit but before measurement as ξout… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

48 extracted references · 34 canonical work pages

  1. [1]

    one-clean qubit

    This problem of approximating the entropy of a state to within a multiplicative precision, which is generally more difficult than additive approximation, has not been discussed in the quantum algorithm literature to the best of our knowledge. We provide a comparison be- tween our work and some of the known results in Table I. We thus extend the investigatio...

    work page

  2. [2]

    Müller-Lennert, F

    M. Müller-Lennert, F. Dupuis, O. Szehr, S. Fehr, and M. Tomamichel, On quantum rényi entropies: A new gen- eralization and some properties, Journal of Mathematical Physics 54, 122203 (2013)

    work page 2013

  3. [3]

    A. Rényi, On measures of entropy and information, in Proceedings of the Fourth Berkeley Symposium on Math- ematical Statistics and Probability, Volume 1: Contribu- tions to the Theory of Statistics (University of California Press, Berkeley, Calif., 1961) pp. 547–561

    work page 1961

  4. [4]

    Clifford and I

    P. Clifford and I. Cosma, A simple sketching algorithm for entropy estimation over streaming data, in Proceed- ings of the Sixteenth International Conference on Arti- ficial Intelligence and Statistics , Proceedings of Machine Learning Research, Vol. 31, edited by C. M. Carvalho and P. Ravikumar (PMLR, Scottsdale, Arizona, USA, 2013) pp. 196–206

    work page 2013

  5. [5]

    Kim, Low complexity estimation method of rényi entropy for ergodic sources, Entropy 20, 657 (2018)

    Y.-S. Kim, Low complexity estimation method of rényi entropy for ergodic sources, Entropy 20, 657 (2018)

    work page 2018

  6. [6]

    Calabrese, J

    P. Calabrese, J. Cardy, and B. Doyon, Entanglement en- tropy in extended quantum systems, Journal of Physics A: Mathematical and Theoretical 42, 500301 (2009)

    work page 2009

  7. [7]

    H. Zhao, A. Lall, M. Ogihara, O. Spatscheck, J. Wang, and J. Xu, A data streaming algorithm for estimating en- tropies of od flows, in Proceedings of the 7th ACM SIG- COMM Conference on Internet Measurement , IMC ’07 (Association for Computing Machinery, New York, NY, USA, 2007) p. 279–290

    work page 2007

  8. [8]

    Schumacher, Quantum coding, Phys

    B. Schumacher, Quantum coding, Phys. Rev. A 51, 2738 (1995)

    work page 1995

Show all 48 references
  1. [9]

    Note that when the density matrix has a non-trivial kernel, the maximum entropy can be O(1) independent of the dimension

    in order to bound these. Note that when the density matrix has a non-trivial kernel, the maximum entropy can be O(1) independent of the dimension. For example if we take δ = 1/4, the uniform distribution over the remaining d − 1 dimensions is excluded from our consideration fo...

    2010

  2. [10]

    Konig, R

    R. Konig, R. Renner, and C. Schaffner, The operational meaning of min- and max-entropy, IEEE Transactions on Information Theory 55, 4337 (2009)

    2009

  3. [11]

    Laflorencie, Quantum entanglement in condensed mat- ter systems, Physics Reports 646, 1 (2016)

    N. Laflorencie, Quantum entanglement in condensed mat- ter systems, Physics Reports 646, 1 (2016)

    2016

  4. [12]

    J. D. Bekenstein, Black holes and entropy, Physical Re- view D 7, 2333 (1973)

    1973

  5. [13]

    Dong, The gravity dual of rényi entropy, Nature Com- munications 7, 10.1038/ncomms12472 (2016)

    X. Dong, The gravity dual of rényi entropy, Nature Com- munications 7, 10.1038/ncomms12472 (2016)

    2016 doi

  6. [14]

    Azuma and S

    K. Azuma and S. Subramanian, Do black holes store neg- ative entropy? (2018), arXiv:1807.06753

    2018 arXiv

  7. [15]

    Azuma and G

    K. Azuma and G. Kato, Second law of black hole ther- modynamics (2020), arXiv:2001.02897

    2020 arXiv

  8. [16]

    T. Batu, S. Dasgupta, R. Kumar, and R. Rubinfeld, The complexity of approximating the entropy, Proceedings of the Annual IEEE Conference on Computational Com- plexity 10.1109/CCC.2002.1004329 (2002)

    2002 arXiv

  9. [17]

    Wu and P

    Y. Wu and P. Yang, Minimax rates of entropy estima- tion on large alphabets via best polynomial approxima- tion, IEEE Transactions on Information Theory 62, 3702 (2016). 10

    2016

  10. [18]

    J. Jiao, K. Venkat, Y. Han, and T. Weissman, Minimax estimation of functionals of discrete distributions, IEEE Transactions on Information Theory 61, 2835 (2015)

    2015

  11. [19]

    Valiant and P

    G. Valiant and P. Valiant, The power of linear estimators, in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (2011) pp. 403–412

    2011

  12. [20]

    M. B. Hastings, I. González, A. B. Kallin, and R. G. Melko, Measuring renyi entanglement entropy in quan- tum Monte Carlo simulations, Physical Review Letters 104, 157201 (2010)

    2010

  13. [21]

    Acharya, I

    J. Acharya, I. Issa, N. V. Shende, and A. B. Wagner, Measuring Quantum Entropy, 2019 IEEE International Symposium on Information Theory (ISIT) , , 3012 (2017), arXiv:1711.00814

    2017 arXiv

  14. [22]

    Islam, R

    R. Islam, R. Ma, P. M. Preiss, M. E. Tai, A. Lukin, M. Rispoli, and M. Greiner, Measuring entanglement en- tropy in a quantum many-body system, Nature 528, 77 (2015)

    2015

  15. [23]

    Li and X

    T. Li and X. Wu, Quantum Query Complexity of Entropy Estimation, IEEE Transactions on Information Theory 65, 2899 (2019)

    2019

  16. [24]

    Gilyén and T

    A. Gilyén and T. Li, Distributional property testing in a quantum world, , 1 (2019) , arXiv:1902.00814

    2019 arXiv

  17. [25]

    Brassard, P

    G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, Quantum amplitude amplification and estimation, Quantum Com- putation and Information, Contemporary Mathematics 305, 53 (2002) , arXiv:0005055 [quant-ph]

    2002

  18. [26]

    Valiant, Testing symmetric properties of distributions , SIAM Journal on Computing 40, 1927 (2011)

    P. Valiant, Testing symmetric properties of distributions , SIAM Journal on Computing 40, 1927 (2011)

    2011

  19. [27]

    A. N. Chowdhury, R. D. Somma, and Y. Subasi, Com- puting partition functions in the one clean qubit model, (2019), arXiv:1910.11842 [quant-ph]

    2019 arXiv

  20. [28]

    Chakraborty, A

    S. Chakraborty, A. Gilyén, and S. Jeffery, The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation, 46th In- ternational Colloquium on Automata, Languages, and Programming (ICALP 2019) , Leibniz International Proceedings in Inf...

    2019 arXiv

  21. [29]

    Gilyén, Y

    A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, Proceedings of the Annual ACM Symposium on Theory of Computing 10.1145/3313276.3316366, arXiv:1806.01838

  22. [30]

    Knill and R

    E. Knill and R. Laflamme, Power of one bit of quantum information, Physical Review Letters 81, 5672 (1998) , arXiv:9802037 [quant-ph]

    1998

  23. [31]

    Passante, On Experimental Deterministic Quantum Computation with One Quantum Bit (DQC1) , Ph.D

    G. Passante, On Experimental Deterministic Quantum Computation with One Quantum Bit (DQC1) , Ph.D. the- sis (2012)

    2012

  24. [32]

    B. P. Lanyon, M. Barbieri, M. P. Almeida, and A. G. White, Experimental quantum computing without entan- glement, Phys. Rev. Lett. 101, 200501 (2008)

    2008

  25. [33]

    A. Belovs, Quantum Algorithms for Classical Probability Distributions, 27th Annual European Symposium on Al- gorithms (ESA 2019) , Leibniz International Proceedings in Informatics (LIPIcs), 144, 16:1 (2019)

    2019

  26. [34]

    G. H. Low and I. L. Chuang, Optimal Hamiltonian Sim- ulation by Quantum Signal Processing, Physical Review Letters 118, 010501 (2017) , arXiv:1610.06546

    2017 arXiv

  27. [35]

    A. W. Harrow, A. Hassidim, and S. Lloyd, Quantum Al- gorithm for Linear Systems of Equations, Physical Re- view Letters 103, 150502 (2009)

    2009

  28. [36]

    Subramanian, S

    S. Subramanian, S. Brierley, and R. Jozsa, Implementing smooth functions of a hermitian matrix on a quantum computer, Journal of Physics Communications 3, 065002 (2019), arXiv:1806.06885

    2019 arXiv

  29. [37]

    L. J. Schulman and U. V. Vazirani, Molecular scale heat engines and scalable quantum computation, in Proceed- ings of the Thirty-first Annual ACM Symposium on The- ory of Computing , STOC ’99 (ACM, New York, NY, USA, 1999) pp. 322–329

    1999

  30. [38]

    S. P. Jordan, Quantum Computation Beyond the Circuit Model, Ph.D. thesis (2008), arXiv:0809.2307

    2008 arXiv

  31. [39]

    Datta, A

    A. Datta, A. Shaji, and C. M. Caves, Quantum discord and the power of one qubit, Phys. Rev. Lett. 100, 050502 (2008)

    2008

  32. [40]

    Morimae, K

    T. Morimae, K. Fujii, and J. F. Fitzsimons, Hardness of classically simulating the one-clean-qubit model, Phys. Rev. Lett. 112, 130502 (2014)

    2014

  33. [41]

    Fujii, H

    K. Fujii, H. Kobayashi, T. Morimae, H. Nishimura, S. Ta- mate, and S. Tani, Impossibility of classically simulat- ing one-clean-qubit model with multiplicative error, Phys. Rev. Lett. 120, 200502 (2018)

    2018

  34. [42]

    P. W. Shor and S. P. Jordan, Estimating jones polynomi- als is a complete problem for one clean qubit, Quantum Info. Comput. 8, 681 (2008)

    2008

  35. [43]

    Cade and A

    C. Cade and A. Montanaro, The Quantum Complex- ity of Computing Schatten p-norms, in 13th Confer- ence on the Theory of Quantum Computation, Commu- nication and Cryptography (TQC 2018) , Leibniz Inter- national Proceedings in Informatics (LIPIcs), Vol. 111, edited by S. Jeffery...

    2018

  36. [44]

    A. K. Ekert, C. M. Alves, D. K. L. Oi, M. Horodecki, P. Horodecki, and L. C. Kwek, Direct estimations of lin- ear and nonlinear functionals of a quantum state, Phys. Rev. Lett. 88, 217901 (2002)

    2002

  37. [45]

    Aharonov, V

    D. Aharonov, V. Jones, and Z. Landau, A polynomial quantum algorithm for approximating the jones polyno- mial, in Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing , STOC ’06 (Asso- ciation for Computing Machinery, New York, NY, USA,

  38. [47]

    Elben, B

    A. Elben, B. Vermersch, M. Dalmonte, J. I. Cirac, and P. Zoller, Rényi entropies from random quenches in atomic hubbard and spin models, Phys. Rev. Lett. 120, 050406 (2018)

    2018

  39. [48]

    Brydges, A

    T. Brydges, A. Elben, P. Jurcevic, B. Vermersch, C. Maier, B. P. Lanyon, P. Zoller, R. Blatt, and C. F. Roos, Probing rényi entanglement entropy via randomized measurements, Science 364, 260 (2019) , arXiv:1806.05747. Appendix A: Implementing power functions of density matrice...

    2019 arXiv

  40. [2006]

    427–436, arXiv:quant-ph/0511096

    p. 427–436, arXiv:quant-ph/0511096

    arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.