Provable quantum advantage in randomness processing

Article, Preprint English OPEN
Dale, H; Jennings, D; Rudolph, T;
(2015)
  • Publisher: Nature Publishing Group
  • Related identifiers: doi: 10.1038/ncomms9203
  • Subject: Physical sciences | Theoretical physics | Quantum Physics

Quantum advantage is notoriously hard to find and even harder to prove. For example the class of functions computable with classical physics actually exactly coincides with the class computable quantum-mechanically. It is strongly believed, but not proven, that quantum ... View more
  • References (19)
    19 references, page 1 of 2

    [1] J. Von Neumann. Various techniques used in connection with random digits. Applied Math Series, 12(36-38), 1951

    [2] M. S. Keane and G. L. O'Brien. A Bernoulli factory. ACM Trans. Model. Comput. Simul. 4(2):213-219, April 1994

    [3] S. Asmussen, P. Glynn and H. Thorisson, Stationarity detection in the initial transient problem. ACM Transactions on Modeling and Computer Simulation 2(2):130-157, 1992

    [4] K. Latuszynski, I. Kosmidis, O. Papaspiliopoulos and G. O. Roberts. Simulating events of unknown probabilities via reverse time martingales. Random Structures and Algorithms, 38(4):441-452, 2011

    [5] J. Wastlund. Function arising by coin-flipping. Technical Report. KTH, Stockholm, 1999

    [6] A. C. Thomas and J. H. Blanchet. A Practical Implementation of the Bernoulli Factory. Preprint at http://arxiv.org/abs/1106.2508 (2011)

    [7] S. Nacu and Y. Peres. Fast simulation of new coins from old. The Annals of Applied Probability, 15(1A):93-115, 2005

    [8] ] E. Mossel and Y. Peres. New coins from old: computing with unknown bias. Combinatorica, 25(6):707-724, 2005.

    [12] Chen-Fu Chiang, Daniel Nagaj, and Pawel Wocjan. 2010. Efficient circuits for quantum walks. Quantum Info. Comput. 10, 5 (May 2010), 420-434

    [13] A. W. Harrow, A. Hassidim and S. Lloyd. Quantum algorithm for linear systems of equations. PRL, 103(15):150502, 2009

  • Metrics
    0
    views in OpenAIRE
    0
    views in local repository
    167
    downloads in local repository

    The information is available from the following content providers:

    FromNumber Of ViewsNumber Of Downloads
    Spiral - Imperial College Digital Repository - IRUS-UK 0 167
Share - Bookmark