{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,20]],"date-time":"2024-08-20T17:07:59Z","timestamp":1724173679448},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2006,4,1]],"date-time":"2006-04-01T00:00:00Z","timestamp":1143849600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2006,4]]},"DOI":"10.1007\/s11128-006-0013-6","type":"journal-article","created":{"date-parts":[[2006,6,2]],"date-time":"2006-06-02T19:15:15Z","timestamp":1149275715000},"page":"83-130","source":"Crossref","is-referenced-by-count":7,"title":["The Quantum Setting with Randomized Queries for Continuous Problems"],"prefix":"10.1007","volume":"5","author":[{"given":"H.","family":"Wo\u017aniakowski","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2006,6,3]]},"reference":[{"key":"13_CR1","first-page":"3","volume":"4","author":"N.S. Bakhvalov","year":"1959","unstructured":"Bakhvalov N.S. (1959). On approximate calculation of integrals (in Russian), Vestnik MGV. Ser. Mat. Mekh. Aston. Fiz. Khim. 4:3\u201318","journal-title":"Ser. Mat. Mekh. Aston. Fiz. Khim."},{"key":"13_CR2","unstructured":"Beals R., Buhrman H., Cleve R., Mosca R., and R. de Wolf, Quantum lower bounds by polynomials, Proc. FOCS\u201998 352\u2013361 (1988). Also http:\/\/arXiv.org\/quant-ph\/9802049."},{"key":"13_CR3","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E. Bernstein","year":"1997","unstructured":"Bernstein E., and Vazirani U. (1997). Quantum complexity theory. SIAM J. Comput. 26:1411\u20131473","journal-title":"SIAM J. Comput."},{"issue":"4","key":"13_CR4","doi-asserted-by":"crossref","first-page":"042313","DOI":"10.1103\/PhysRevA.71.042313","volume":"71","author":"A.J. Bessen","year":"2005","unstructured":"Bessen A.J. (2005). A lower bound for phase estimation on a quantum computer, Phys. Rev. A 71(4):042313 Also http:\/\/arXiv.org\/quant-ph\/0412008.","journal-title":"Phys. Rev. A"},{"key":"13_CR5","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1090\/conm\/305\/05215","volume":"305","author":"G. Brassard","year":"2002","unstructured":"Brassard G., Hoyer P., Mosca M., and Tapp A. (2002). Quantum amplitude amplification and estimation. Contemp. Math. Am. Math. Soc. 305:53\u201374 Also http:\/\/arXiv.org\/quant-ph\/0005055.","journal-title":"Contemp. Math. Am. Math. Soc."},{"key":"13_CR6","doi-asserted-by":"crossref","first-page":"474","DOI":"10.1006\/jcom.2000.0545","volume":"16","author":"F. Curbera","year":"2000","unstructured":"Curbera F. (2000). Delayed curse of dimension for Gaussian integration. J. Complexity 16:474\u2013506","journal-title":"J. Complexity"},{"issue":"1","key":"13_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jcom.2001.0629","volume":"18","author":"S. Heinrich","year":"2002","unstructured":"Heinrich S. (2002). Quantum summation with an application to integration. J. Complexity 18(1):1\u201350 Also http:\/\/arXiv.org\/quant-ph\/0105116.","journal-title":"J. Complexity"},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0885-064X(02)00008-0","volume":"19","author":"S. Heinrich","year":"2003","unstructured":"Heinrich S. (2003). Quantum integration in Sobolev spaces. J. Complexity 19:19\u201342","journal-title":"J. Complexity"},{"key":"13_CR9","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.jco.2003.08.002","volume":"20","author":"S. Heinrich","year":"2004","unstructured":"Heinrich S. (2004). Quantum approximation I. embeddings of finite dimensional L p spaces. J. Complexity 20:5\u201326 Also http:\/\/arXiv.org\/quant-ph\/0305030","journal-title":"J. Complexity"},{"key":"13_CR10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.jco.2003.08.003","volume":"20","author":"S. Heinrich","year":"2004","unstructured":"Heinrich S. (2004). Quantum approximation II. Sobolev embeddings. J. Complexity 20:27\u201345 Also http:\/\/arXiv.org\/quant-ph\/0305031.","journal-title":"J. Complexity"},{"key":"13_CR11","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/978-3-642-18743-8_14","volume-title":"Monte Carlo and Quasi-Monte Carlo Methods 2002","author":"S. Heinrich","year":"2004","unstructured":"Heinrich S., Kwas M., and Wo\u017aniakowski H. (2004). Quantum Boolean Summation with Repetitions in the Worst-average case Setting. In: Niederreiter H. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2002. Springer Verlag, Berlin, pp 243\u2013258"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Heinrich S., On the power of quantum algorithms for vector valued mean computation, submitted for publication, 2004. See http:\/\/arXiv.org\/quant-ph\/04031109.","DOI":"10.1515\/mcma.2004.10.3-4.297"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Heinrich S., Novak E., and Pfeiffer H. How many Random Bits do we Need for Monte Carlo Integration?. In: Niederreiter H. (eds) Monte Carlo and Quasi-Monte Carlo Methods 2002, Proceedings of a conference held at the national University of Singapore, November, 2002 (Springer, Berlin, 27\u201349).","DOI":"10.1007\/978-3-642-18743-8_2"},{"key":"13_CR14","doi-asserted-by":"crossref","first-page":"257902","DOI":"10.1103\/PhysRevLett.91.257902","volume":"91","author":"P. Jaksch","year":"2003","unstructured":"Jaksch P., and Papageorgiou A. (2003). Eigenvector approximation leading to exponential speedup of quantum eigenvalue calculation. Phys. Rev. Lett. 91:257902 Also http:\/\/arXiv.org\/quant-ph\/0308016","journal-title":"Phys. Rev. Lett."},{"key":"13_CR15","doi-asserted-by":"crossref","first-page":"740","DOI":"10.1016\/j.jco.2005.05.003","volume":"21","author":"B.Z. Kacewicz","year":"2005","unstructured":"Kacewicz B.Z. (2005). Improved bounds on the randomized and quantum complexity of initial value problems. J. Complexity 21:740\u2013756","journal-title":"J. Complexity"},{"key":"13_CR16","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1016\/j.jco.2003.08.004","volume":"20","author":"M. Kwas","year":"2004","unstructured":"Kwas M., and Wo\u017aniakowski H. (2004). Sharp error bounds on quantum Boolean summation in various settings. J. Complexity 20:669\u2013698","journal-title":"J. Complexity"},{"key":"13_CR17","volume-title":"Approximation of Functions","author":"G. Lorentz","year":"1966","unstructured":"Lorentz G. (1966). Approximation of Functions. Holt, New York"},{"key":"13_CR18","doi-asserted-by":"crossref","unstructured":"Nayak A., and Wu F., The quantum query complexity of approximating the median and related statistics, in Proceedings of the 31th Annual ACM Symposium on the Theory of Computing (STOC), pp. 384\u2013393, 1999. Also http:\/\/arXiv.org\/quant-ph\/9804066.","DOI":"10.1145\/301250.301349"},{"key":"13_CR19","doi-asserted-by":"crossref","unstructured":"Niederreiter H., Random number generation and Quasi-Monte Carlo methods, in Proc. vol. 63 of SIAM CBMS-NSF Regional Conference Series in Applied Mathematics (SIAM, Philadelphia, 1992).","DOI":"10.1137\/1.9781611970081"},{"key":"13_CR20","volume-title":"Quantum Computation and Quantum Information","author":"M.A. Nielsen","year":"2000","unstructured":"Nielsen M.A., and Chuang I.L. (2000). Quantum Computation and Quantum Information. Cambridge University Press, Cambridge"},{"key":"13_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0079792","volume-title":"Deterministic and Stochastic Error Bounds in Numerical Analysis","author":"E. Novak","year":"1988","unstructured":"Novak E. (1988). Deterministic and Stochastic Error Bounds in Numerical Analysis. Lecture Notes in Mathematics 1349, Springer-Verlag, Berlin"},{"key":"13_CR22","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1016\/0885-064X(92)90032-7","volume":"8","author":"E. Novak","year":"1992","unstructured":"Novak E. (1992). Optimal linear randomized methods for linear operators in Hilbert spaces. J. Complexity 8:22\u201336","journal-title":"J. Complexity"},{"key":"13_CR23","first-page":"211","volume-title":"Foundation of Computational Mathematics, Oxford, 1999","author":"E. Novak","year":"2001","unstructured":"Novak E., and Wo\u017aniakowski H. (2001). When are integration and discrepancy tractable?. In: DeVore R.A., Iserles A., S\u00fcli E. (eds) Foundation of Computational Mathematics, Oxford, 1999. Cambridge University Press, Cambridge, pp. 211\u2013266"},{"key":"13_CR24","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1006\/jcom.2000.0566","volume":"17","author":"E. Novak","year":"2001","unstructured":"Novak E. (2001). Quantum complexity of integration. J. Complexity 17:2\u201316 Also http:\/\/arXiv.org\/quant-ph\/0008124.","journal-title":"J. Complexity"},{"key":"13_CR25","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1016\/j.jco.2003.08.005","volume":"20","author":"A. Papageorgiou","year":"2004","unstructured":"Papageorgiou A. (2004). Average case quantum lower bounds for computing the Boolean mean. J. Complexity 20:713\u2013731","journal-title":"J. Complexity"},{"issue":"2","key":"13_CR26","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s11128-005-4481-x","volume":"4","author":"A. Papageorgiou","year":"2005","unstructured":"Papageorgiou A., and Wo\u017aniakowski H. (2005). Classical and quantum complexity of the Sturm-Liouville eigenvalue problem. Quantum Inf. Process. 4(2):87\u2013127 Also http:\/\/arXiv.org\/quant-ph\/0502054.","journal-title":"Quantum Inf. Process."},{"key":"13_CR27","volume-title":"Monte Carlo with few random bits","author":"H. Pfeiffer","year":"2005","unstructured":"Pfeiffer H. (2005). Monte Carlo with few random bits. PhD Thesis, University of Jena, Shaker Verlag Aachen"},{"key":"13_CR28","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511600814","volume-title":"Noisy Information and Computational Complexity","author":"L. Plaskota","year":"1996","unstructured":"Plaskota L. (1996). Noisy Information and Computational Complexity. Cambridge University Press, Cambridge"},{"key":"13_CR29","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198534723.001.0001","volume-title":"Lattice Methods for Multiple Integration","author":"I.H. Sloan","year":"1994","unstructured":"Sloan I.H., and Joe S. (1994). Lattice Methods for Multiple Integration. Clarendon press, Oxford"},{"issue":"5","key":"13_CR30","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor P.W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithm on a quantum computer. SIAM J. Comput. 26(5):1484\u20131509","journal-title":"SIAM J. Comput."},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Traub J.F., A continuous model of computation, Phys. Today May, 39\u201343 (1999).","DOI":"10.1063\/1.882660"},{"key":"13_CR32","volume-title":"Information-Based Complexity","author":"J.F. Traub","year":"1988","unstructured":"Traub J.F., Wasilkowski G.W., and Wo\u017aniakowski H. (1988). Information-Based Complexity. Academic Press, New York"},{"key":"13_CR33","volume-title":"Complexity and Information","author":"J.F. Traub","year":"1998","unstructured":"Traub J.F., and Werschulz A.G. (1998). Complexity and Information. Cambridge University Press, Cambridge"},{"key":"13_CR34","volume-title":"A General Theory of Optimal Algorithms","author":"J.F. Traub","year":"1980","unstructured":"Traub J.F., and Wo\u017aniakowski H. (1980). A General Theory of Optimal Algorithms. Academic Press, New York"},{"issue":"5","key":"13_CR35","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1023\/A:1023417813916","volume":"1","author":"J.F. Traub","year":"2002","unstructured":"Traub J.F., and Wo\u017aniakowski H. (2002). Path integration on a quantum computer. Quantum Inf. Process. 1(5):365\u2013388 Also http:\/\/arXiv.org\/quant-ph\/0109113","journal-title":"Quantum Inf. Process."},{"key":"13_CR36","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1006\/jcom.1993.1021","volume":"9","author":"G.W. Wasilkowski","year":"1993","unstructured":"Wasilkowski G.W., and Wo\u017aniakowski H. (1993). There exists a linear problem with infinite combinatory complexity. J. Complexity 9:326\u2013337","journal-title":"J. Complexity"},{"issue":"4","key":"13_CR37","doi-asserted-by":"crossref","first-page":"2071","DOI":"10.1063\/1.531493","volume":"37","author":"G.W. Wasilkowski","year":"1996","unstructured":"Wasilkowski G.W., and Wo\u017aniakowski H. (1996). On tractability of path integration. J. Math. Phys. 37(4):2071\u20132088","journal-title":"J. Math. Phys."},{"key":"13_CR38","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198535898.001.0001","volume-title":"The Computational Complexity of Differential and Integral Equations: An Information-Based Approach","author":"A.G. Werschulz","year":"1991","unstructured":"Werschulz A.G. (1991). The Computational Complexity of Differential and Integral Equations: An Information-Based Approach. Oxford University Press, New York"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-006-0013-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-006-0013-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-006-0013-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,4]],"date-time":"2024-02-04T17:17:02Z","timestamp":1707067022000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-006-0013-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,4]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,4]]}},"alternative-id":["13"],"URL":"https:\/\/doi.org\/10.1007\/s11128-006-0013-6","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,4]]}}}