{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T11:57:12Z","timestamp":1781870232190,"version":"3.54.5"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T00:00:00Z","timestamp":1781827200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T00:00:00Z","timestamp":1781827200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"ANR JCJC DisQC","award":["ANR-22-CE47-0002-01"],"award-info":[{"award-number":["ANR-22-CE47-0002-01"]}]},{"name":"PEPR EPiQ","award":["ANR-22-PETQ-0007"],"award-info":[{"award-number":["ANR-22-PETQ-0007"]}]},{"name":"QuanTEdu-France","award":["ANR-22-CMAS-0001"],"award-info":[{"award-number":["ANR-22-CMAS-0001"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Mach. Intell."],"published-print":{"date-parts":[[2026,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    With the growing interest in quantum machine learning, the perceptron, a fundamental building block in traditional machine learning, has emerged as a valuable model for exploring the potential of quantum algorithms. In this work, we make two principal contributions. First, we revisit the\n                    <jats:italic>quantum version space perceptron<\/jats:italic>\n                    algorithm proposed by Kapoor et al. (2016), by identifying and correcting a flawed complexity assumption. We show that the query complexity of the algorithm is dimension-dependent, which has significant implications for its behaviour in high-dimensional regimes under worst-case scenarios. Second, we propose and analyse two\n                    <jats:italic>quantum-enhanced<\/jats:italic>\n                    cutting-plane algorithms for perceptron learning. Specifically, we leverage established quantum subroutines such as\n                    <jats:italic>Grover\u2019s search<\/jats:italic>\n                    and\n                    <jats:italic>quantum walk search<\/jats:italic>\n                    , and provide detailed algorithmic constructions together with query and arithmetic complexity analyses. Our results establish improved complexity bounds under an idealised implementation framework and noise-free quantum computational models, offering insights into the trade-offs between margin dependence, dimensional dependence, and quantum resources. These findings provide a refined understanding of quantum perceptron models and their theoretical computational complexity properties.\n                  <\/jats:p>","DOI":"10.1007\/s42484-026-00406-4","type":"journal-article","created":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T11:47:19Z","timestamp":1781869639000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On quantum perceptron learning via quantum search"],"prefix":"10.1007","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-1249-142X","authenticated-orcid":false,"given":"Xiaoyu","family":"Sun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3890-1552","authenticated-orcid":false,"given":"Mathieu","family":"Roget","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1261-7476","authenticated-orcid":false,"given":"Giuseppe","family":"Di Molfetta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8060-5354","authenticated-orcid":false,"given":"Hachem","family":"Kadri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,19]]},"reference":[{"issue":"4","key":"406_CR1","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1038\/nphys3272","volume":"11","author":"S Aaronson","year":"2015","unstructured":"Aaronson S (2015) Read the fine print. Nat Phys 11(4):291\u2013293. https:\/\/doi.org\/10.1038\/nphys3272","journal-title":"Nat Phys"},{"key":"406_CR2","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/780542.780546","volume-title":"Proceedings of the thirty-fifth annual ACM symposium on theory of computing, STOC \u201903","author":"D Aharonov","year":"2003","unstructured":"Aharonov D, Ta-Shma A (2003) Adiabatic quantum state generation and statistical zero knowledge. Proceedings of the thirty-fifth annual ACM symposium on theory of computing, STOC \u201903. pp 20\u201329. https:\/\/doi.org\/10.1145\/780542.780546"},{"issue":"1","key":"406_CR3","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1137\/25M1736098","volume":"55","author":"S Apers","year":"2026","unstructured":"Apers S, Gribling S (2026) Quantum speedups for linear programming via interior point methods. SIAM J Comput 55(1):93\u2013134. https:\/\/doi.org\/10.1137\/25M1736098","journal-title":"SIAM J Comput"},{"issue":"1","key":"406_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF01585551","volume":"69","author":"DS Atkinson","year":"1995","unstructured":"Atkinson DS, Vaidya PM (1995) A cutting plane algorithm for convex programming that uses analytic centers. Math Program 69(1):1\u201343. https:\/\/doi.org\/10.1007\/BF01585551","journal-title":"Math Program"},{"issue":"4","key":"406_CR5","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1145\/1008731.1008733","volume":"51","author":"D Bertsimas","year":"2004","unstructured":"Bertsimas D, Vempala S (2004) Solving convex programs by random walks. J ACM 51(4):540\u2013556. https:\/\/doi.org\/10.1145\/1008731.1008733","journal-title":"J ACM"},{"issue":"7671","key":"406_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1038\/nature23474","volume":"549","author":"J Biamonte","year":"2017","unstructured":"Biamonte J, Wittek P, Pancotti N et al (2017) Quantum machine learning. Nature 549(7671):195\u2013202. https:\/\/doi.org\/10.1038\/nature23474","journal-title":"Nature"},{"key":"406_CR7","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1103\/RevModPhys.34.123","volume":"34","author":"HD Block","year":"1962","unstructured":"Block HD (1962) The perceptron: a model for brain functioning. i. Rev Mod Phys 34:123\u2013135. https:\/\/doi.org\/10.1103\/RevModPhys.34.123","journal-title":"Rev Mod Phys"},{"key":"406_CR8","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1007\/BFb0055105","volume-title":"Automata, Languages and Programming","author":"G Brassard","year":"1998","unstructured":"Brassard G, H\u00f8yer P, Tapp A (1998) Quantum counting. Automata, Languages and Programming. pp 820\u2013831. https:\/\/doi.org\/10.1007\/BFb0055105"},{"key":"406_CR9","unstructured":"Brassard G, H\u00f8yer P, Mosca M (2000) Quantum amplitude amplification and estimation. arXiv:quant-ph\/0005055"},{"key":"406_CR10","doi-asserted-by":"publisher","first-page":"167902","DOI":"10.1103\/PhysRevLett.87.167902","volume":"87","author":"H Buhrman","year":"2001","unstructured":"Buhrman H, Cleve R, Watrous J et al (2001) Quantum fingerprinting. Phys Rev Lett 87:167902. https:\/\/doi.org\/10.1103\/PhysRevLett.87.167902","journal-title":"Phys Rev Lett"},{"key":"406_CR11","doi-asserted-by":"publisher","unstructured":"Chakrabarti S, Childs AM, Hung SH (2023) Quantum algorithm for estimating volumes of convex bodies. ACM Trans Quantum Comput 4(3). https:\/\/doi.org\/10.1145\/3588579","DOI":"10.1145\/3588579"},{"issue":"1969","key":"406_CR12","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1098\/rspa.1998.0164","volume":"454","author":"R Cleve","year":"1998","unstructured":"Cleve R, Ekert A, Macchiavello C et al (1998) Quantum algorithms revisited. Proc R Soc London Ser A Math Phys Eng Sci 454(1969):339\u2013354. https:\/\/doi.org\/10.1098\/rspa.1998.0164","journal-title":"Proc R Soc London Ser A Math Phys Eng Sci"},{"key":"406_CR13","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/1.9781611977554.ch46","volume-title":"Proceedings of the 2023 annual ACM-SIAM symposium on discrete algorithms (SODA), SIAM","author":"A Cornelissen","year":"2023","unstructured":"Cornelissen A, Hamoudi Y (2023) A sublinear-time quantum algorithm for approximating partition functions. Proceedings of the 2023 annual ACM-SIAM symposium on discrete algorithms (SODA), SIAM. pp 1245\u20131264. https:\/\/doi.org\/10.1137\/1.9781611977554.ch46"},{"key":"406_CR14","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1145\/3519935.3520045","volume-title":"Proceedings of the 54th Annual ACM SIGACT symposium on theory of computing, STOC 2022","author":"A Cornelissen","year":"2022","unstructured":"Cornelissen A, Hamoudi Y, Jerbi S (2022) Near-optimal quantum algorithms for multivariate mean estimation. Proceedings of the 54th Annual ACM SIGACT symposium on theory of computing, STOC 2022. pp 33\u201343. https:\/\/doi.org\/10.1145\/3519935.3520045"},{"issue":"1","key":"406_CR15","doi-asserted-by":"publisher","first-page":"81","DOI":"10.26421\/QIC6.1-6.arXiv:quant-ph\/0505030v2","volume":"6","author":"CM Dawson","year":"2006","unstructured":"Dawson CM, Nielsen MA (2006) The Solovay-Kitaev algorithm. Quantum Info Comput 6(1):81\u201395. https:\/\/doi.org\/10.26421\/QIC6.1-6.arXiv:quant-ph\/0505030v2","journal-title":"Quantum Info Comput"},{"issue":"2","key":"406_CR16","doi-asserted-by":"publisher","first-page":"023006","DOI":"10.1088\/1367-2630\/17\/2\/023006","volume":"17","author":"V Dunjko","year":"2015","unstructured":"Dunjko V, Friis N, Briegel HJ (2015) Quantum-enhanced deliberation of learning agents using trapped ions. New J Phys 17(2):023006. https:\/\/doi.org\/10.1088\/1367-2630\/17\/2\/023006","journal-title":"New J Phys"},{"issue":"6","key":"406_CR17","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/BF02650179","volume":"21","author":"RP Feynman","year":"1982","unstructured":"Feynman RP (1982) Simulating physics with computers. Int J Theor Phys 21(6):467\u2013488. https:\/\/doi.org\/10.1007\/BF02650179","journal-title":"Int J Theor Phys"},{"issue":"1","key":"406_CR18","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/S0304-3975(01)00079-2","volume":"284","author":"S Fine","year":"2002","unstructured":"Fine S, Gilad-Bachrach R, Shamir E (2002) Query by committee, linear separation and random walks. Theoret Comput Sci 284(1):25\u201351. https:\/\/doi.org\/10.1016\/S0304-3975(01)00079-2","journal-title":"Theoret Comput Sci"},{"key":"406_CR19","unstructured":"Gonen A, Sabato S, Shalev-Shwartz S (2013) Efficient active learning of halfspaces: an aggressive approach. In: Proceedings of the 30th international conference on machine learning, pp 480\u2013488. https:\/\/proceedings.mlr.press\/v28\/gonen13.html"},{"key":"406_CR20","doi-asserted-by":"publisher","unstructured":"Gr\u00f6tschel M, Lov\u00e1sz L, Schrijver A (2012) Geometric algorithms and combinatorial optimization, vol 2. Springer Science & Business Media. https:\/\/doi.org\/10.1007\/978-3-642-78240-4","DOI":"10.1007\/978-3-642-78240-4"},{"key":"406_CR21","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1145\/237814.237866","volume-title":"Proceedings of the twenty-eighth annual ACM symposium on theory of computing, STOC \u201996","author":"LK Grover","year":"1996","unstructured":"Grover LK (1996) A fast quantum mechanical algorithm for database search. Proceedings of the twenty-eighth annual ACM symposium on theory of computing, STOC \u201996. pp 212\u2013219. https:\/\/doi.org\/10.1145\/237814.237866"},{"key":"406_CR22","unstructured":"Grover LK (2005) A different kind of quantum search. arXiv:quant-ph\/0503205"},{"key":"406_CR23","unstructured":"Grover L, Rudolph T (2002) Creating superpositions that correspond to efficiently integrable probability distributions. arXiv:quant-ph\/0208112"},{"key":"406_CR24","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/1.9781611975994.12","volume-title":"Proceedings of the thirty-first annual ACM-SIAM symposium on discrete algorithms, SODA \u201920","author":"AW Harrow","year":"2020","unstructured":"Harrow AW, Wei AY (2020) Adaptive quantum simulated annealing for Bayesian inference and estimating partition functions. Proceedings of the thirty-first annual ACM-SIAM symposium on discrete algorithms, SODA \u201920. pp 193\u2013212. https:\/\/doi.org\/10.1137\/1.9781611975994.12"},{"issue":"15","key":"406_CR25","doi-asserted-by":"publisher","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"AW Harrow","year":"2009","unstructured":"Harrow AW, Hassidim A, Lloyd S (2009) Quantum algorithm for linear systems of equations. Phys Rev Lett 103(15):150502. https:\/\/doi.org\/10.1103\/PhysRevLett.103.150502","journal-title":"Phys Rev Lett"},{"key":"406_CR26","first-page":"245","volume":"1","author":"R Herbrich","year":"2001","unstructured":"Herbrich R, Graepel T, Campbell C (2001) Bayes point machines. J Mach Learn Res 1:245\u2013279","journal-title":"J Mach Learn Res"},{"issue":"5","key":"406_CR27","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1145\/3571725","volume":"66","author":"T Hoefler","year":"2023","unstructured":"Hoefler T, H\u00e4ner T, Troyer M (2023) Disentangling hype from practicality: on realistically achieving quantum advantage. Commun ACM 66(5):82\u201387. https:\/\/doi.org\/10.1145\/3571725","journal-title":"Commun ACM"},{"key":"406_CR28","doi-asserted-by":"publisher","first-page":"944","DOI":"10.1145\/3357713.3384284","volume-title":"Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing","author":"H Jiang","year":"2020","unstructured":"Jiang H, Lee YT, Song Z (2020) An improved cutting plane method for convex optimization, convex-concave games, and its applications. Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, vol 2020. pp 944\u2013953. https:\/\/doi.org\/10.1145\/3357713.3384284"},{"key":"406_CR29","unstructured":"Kapoor A, Wiebe N, Svore K (2016) Quantum perceptron models. Advances in Neural Information Processing Systems"},{"key":"406_CR30","doi-asserted-by":"publisher","unstructured":"Kerenidis I, Prakash A (2020) A quantum interior point method for LPs and SDPs. ACM Trans Quantum Comput 1(1). https:\/\/doi.org\/10.1145\/3406306","DOI":"10.1145\/3406306"},{"key":"406_CR31","doi-asserted-by":"publisher","unstructured":"Khachiyan LG (1979) A polynomial algorithm in linear programming. Doklady Akademii Nauk Russian Acad Sci 1093\u20131096. https:\/\/doi.org\/10.1016\/0041-5553(80)90061-0","DOI":"10.1016\/0041-5553(80)90061-0"},{"key":"406_CR32","doi-asserted-by":"publisher","first-page":"1049","DOI":"10.1109\/FOCS.2015.68","volume-title":"IEEE 56th annual symposium on foundations of computer science","author":"YT Lee","year":"2015","unstructured":"Lee YT, Sidford A, Wong S (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. IEEE 56th annual symposium on foundations of computer science. pp 1049\u20131065. https:\/\/doi.org\/10.1109\/FOCS.2015.68"},{"issue":"1","key":"406_CR33","doi-asserted-by":"publisher","first-page":"66","DOI":"10.3923\/ajms.2011.66.70","volume":"4","author":"S Li","year":"2010","unstructured":"Li S (2010) Concise formulas for the area and volume of a hyperspherical cap. Asian J Math Stat 4(1):66\u201370. https:\/\/doi.org\/10.3923\/ajms.2011.66.70","journal-title":"Asian J Math Stat"},{"key":"406_CR34","unstructured":"Li T, Zhang R (2022) Quantum speedups of optimizing approximately convex functions with applications to logarithmic regret stochastic convex bandits. In: Advances in neural information processing systems, pp 3152\u20133164. https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2022\/file\/14f75513f0f1ca01de1e826b52e6b840-Paper-Conference.pdf"},{"key":"406_CR35","unstructured":"Li X, Song Z, Yu J (2024) Quantum speedups for approximating the john ellipsoid. arXiv:2408.14018"},{"issue":"6","key":"406_CR36","doi-asserted-by":"publisher","first-page":"062412","DOI":"10.1103\/PhysRevA.110.062412","volume":"110","author":"P Liao","year":"2024","unstructured":"Liao P, Sanders BC, Byrnes T (2024) Quadratic quantum speedup for perceptron training. Phys Rev A 110(6):062412. https:\/\/doi.org\/10.1103\/PhysRevA.110.062412","journal-title":"Phys Rev A"},{"key":"406_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/IJCNN.2015.7280694","volume-title":"2015 International joint conference on neural networks (IJCNN)","author":"U Louche","year":"2015","unstructured":"Louche U, Ralaivola L (2015) From cutting planes algorithms to compression schemes and active learning. 2015 International joint conference on neural networks (IJCNN). pp 1\u20138. https:\/\/doi.org\/10.1109\/IJCNN.2015.7280694"},{"key":"406_CR38","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s101070050099","volume":"86","author":"L Lov\u00e1sz","year":"1999","unstructured":"Lov\u00e1sz L (1999) Hit-and-run mixes fast. Math Program 86:443\u2013461. https:\/\/doi.org\/10.1007\/s101070050099","journal-title":"Math Program"},{"key":"406_CR39","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/1250790.1250874","volume-title":"Proceedings of the thirty-ninth annual ACM symposium on theory of computing, STOC \u201907","author":"F Magniez","year":"2007","unstructured":"Magniez F, Nayak A, Roland J (2007) Search via quantum walk. Proceedings of the thirty-ninth annual ACM symposium on theory of computing, STOC \u201907. pp 575\u2013584. https:\/\/doi.org\/10.1145\/1250790.1250874"},{"key":"406_CR40","unstructured":"Minka TP (2001) A family of algorithms for approximate Bayesian inference. Massachusetts Institute of Technology. PhD thesis. http:\/\/hdl.handle.net\/1721.1\/86583"},{"key":"406_CR41","unstructured":"Mohri M, Rostamizadeh A, Talwalkar A (2018) Foundations of machine learning, 2nd edn, The MIT Press. https:\/\/dlib.hust.edu.vn\/server\/api\/core\/bitstreams\/3293054a-2c5f-4c97-bb14-b7c891e16c90\/content"},{"key":"406_CR42","unstructured":"Nemirovski A (1994) Efficient methods in convex programming, Lecture Notes. https:\/\/www2.isye.gatech.edu\/~nemirovs\/"},{"key":"406_CR43","unstructured":"Nemirovskij AS, Yudin DB (1983) Problem complexity and method efficiency in optimization. Wiley-Interscience. https:\/\/www2.isye.gatech.edu\/ nemirovs\/Nemirovskii_Yudin_1983.pdf"},{"key":"406_CR44","doi-asserted-by":"publisher","unstructured":"Nielsen MA, Chuang IL (2010) Quantum computation and quantum information. Cambridge University Press. https:\/\/doi.org\/10.1017\/CBO9780511976667","DOI":"10.1017\/CBO9780511976667"},{"key":"406_CR45","unstructured":"Novikoff AB (1962) On convergence proofs on perceptrons. In: Proceedings of the symposium on the mathematical theory of automata, pp 615\u2013622. https:\/\/apps.dtic.mil\/sti\/tr\/pdf\/AD0298258.pdf"},{"key":"406_CR46","doi-asserted-by":"publisher","unstructured":"Orsucci D, Briegel HJ, Dunjko V (2018) Faster quantum mixing for slowly evolving sequences of Markov chains. 2:105. https:\/\/doi.org\/10.22331\/q-2018-11-09-105","DOI":"10.22331\/q-2018-11-09-105"},{"key":"406_CR47","doi-asserted-by":"publisher","first-page":"773","DOI":"10.1007\/978-3-540-70575-8_63","volume-title":"Automata, languages and programming","author":"O Regev","year":"2008","unstructured":"Regev O, Schiff L (2008) Impossibility of a quantum speed-up with a faulty oracle. Automata, languages and programming. pp 773\u2013781. https:\/\/doi.org\/10.1007\/978-3-540-70575-8_63"},{"key":"406_CR48","unstructured":"Roget M, Molfetta D, Kadri GH (2022) Quantum perceptron revisited: computational-statistical tradeoffs. In: Proceedings of the thirty-eighth conference on uncertainty in artificial intelligence, Proceedings of Machine Learning Research. pp 1697\u20131706. https:\/\/proceedings.mlr.press\/v180\/roget22a.html"},{"issue":"6","key":"406_CR49","doi-asserted-by":"publisher","first-page":"386","DOI":"10.1037\/h0042519","volume":"65","author":"F Rosenblatt","year":"1958","unstructured":"Rosenblatt F (1958) The perceptron: a probabilistic model for information storage and organization in the brain. Psychol Rev 65(6):386. https:\/\/doi.org\/10.1037\/h0042519","journal-title":"Psychol Rev"},{"issue":"1","key":"406_CR50","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1006\/jfan.1998.3384","volume":"164","author":"M Rudelson","year":"1999","unstructured":"Rudelson M (1999) Random vectors in the isotropic position. J Funct Anal 164(1):60\u201372. https:\/\/doi.org\/10.1006\/jfan.1998.3384","journal-title":"J Funct Anal"},{"issue":"7849","key":"406_CR51","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1038\/s41586-021-03242-7","volume":"591","author":"V Saggio","year":"2021","unstructured":"Saggio V, Asenbeck BE, Hamann A et al (2021) Experimental quantum speed-up in reinforcement learning agents. Nature 591(7849):229\u2013233. https:\/\/doi.org\/10.1038\/s41586-021-03242-7","journal-title":"Nature"},{"issue":"2","key":"406_CR52","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1080\/00107514.2014.964942","volume":"56","author":"M Schuld","year":"2015","unstructured":"Schuld M, Sinayskiy I, Petruccione F (2015) An introduction to quantum machine learning. Contemp Phys 56(2):172\u2013185. https:\/\/doi.org\/10.1080\/00107514.2014.964942","journal-title":"Contemp Phys"},{"key":"406_CR53","doi-asserted-by":"publisher","first-page":"032308","DOI":"10.1103\/PhysRevA.101.032308","volume":"101","author":"M Schuld","year":"2020","unstructured":"Schuld M, Bocharov A, Svore KM et al (2020) Circuit-centric quantum classifiers. Phys Rev A 101:032308. https:\/\/doi.org\/10.1103\/PhysRevA.101.032308","journal-title":"Phys Rev A"},{"key":"406_CR54","doi-asserted-by":"publisher","first-page":"052313","DOI":"10.1103\/PhysRevA.68.052313","volume":"68","author":"N Shenvi","year":"2003","unstructured":"Shenvi N, Brown KR, Whaley KB (2003) Effects of a random noisy oracle on search algorithm complexity. Phys Rev A 68:052313. https:\/\/doi.org\/10.1103\/PhysRevA.68.052313","journal-title":"Phys Rev A"},{"issue":"6","key":"406_CR55","doi-asserted-by":"publisher","first-page":"1296","DOI":"10.1287\/opre.32.6.1296","volume":"32","author":"RL Smith","year":"1984","unstructured":"Smith RL (1984) Efficient Monte Carlo procedures for generating points uniformly distributed over bounded regions. Oper Res 32(6):1296\u20131308","journal-title":"Oper Res"},{"key":"406_CR56","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1109\/FOCS.2004.53","volume-title":"45th Annual IEEE Symposium on Foundations of Computer Science","author":"M Szegedy","year":"2004","unstructured":"Szegedy M (2004) Quantum speed-up of Markov chain based algorithms. 45th Annual IEEE Symposium on Foundations of Computer Science. IEEE, pp 32\u201341. https:\/\/doi.org\/10.1109\/FOCS.2004.53"},{"key":"406_CR57","first-page":"45","volume":"2","author":"S Tong","year":"2001","unstructured":"Tong S, Koller D (2001) Support vector machine active learning with applications to text classification. J Mach Learn Res 2:45\u201366","journal-title":"J Mach Learn Res"},{"key":"406_CR58","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1109\/SFCS.1989.63500","volume-title":"IEEE 54th Annual Symposium on Foundations of Computer Science","author":"P Vaidya","year":"1989","unstructured":"Vaidya P (1989) A new algorithm for minimizing convex functions over convex sets. IEEE 54th Annual Symposium on Foundations of Computer Science. pp 338\u2013343. https:\/\/doi.org\/10.1109\/SFCS.1989.63500"},{"key":"406_CR59","doi-asserted-by":"publisher","unstructured":"Van Apeldoorn J (2021) Quantum probability oracles & multidimensional amplitude estimation. In: 16th Conference on the theory of quantum computation, communication and cryptography (TQC 2021), Leibniz International Proceedings in Informatics (LIPIcs), pp 9:1\u20139:11. https:\/\/doi.org\/10.4230\/LIPIcs.TQC.2021.9","DOI":"10.4230\/LIPIcs.TQC.2021.9"},{"key":"406_CR60","doi-asserted-by":"publisher","first-page":"220","DOI":"10.22331\/q-2020-01-13-220","volume":"4","author":"J Van Apeldoorn","year":"2020","unstructured":"Van Apeldoorn J, Gily\u00e9n A, Gribling S (2020) Convex optimization using quantum oracles. Quantum 4:220. https:\/\/doi.org\/10.22331\/q-2020-01-13-220","journal-title":"Quantum"},{"key":"406_CR61","doi-asserted-by":"publisher","first-page":"042336","DOI":"10.1103\/PhysRevA.78.042336","volume":"78","author":"P Wocjan","year":"2008","unstructured":"Wocjan P, Abeyesinghe A (2008) Speedup via quantum sampling. Phys Rev A 78:042336. https:\/\/doi.org\/10.1103\/PhysRevA.78.042336","journal-title":"Phys Rev A"},{"key":"406_CR62","doi-asserted-by":"publisher","first-page":"1153","DOI":"10.1145\/1553374.1553521","volume-title":"Proceedings of the 26th annual international conference on machine learning, ICML \u201909","author":"L Yang","year":"2009","unstructured":"Yang L, Jin R, Ye J (2009) Online learning by ellipsoid method. Proceedings of the 26th annual international conference on machine learning, ICML \u201909. pp 1153\u20131160. https:\/\/doi.org\/10.1145\/1553374.1553521"}],"container-title":["Quantum Machine Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-026-00406-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s42484-026-00406-4","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s42484-026-00406-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T11:47:27Z","timestamp":1781869647000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s42484-026-00406-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,19]]},"references-count":62,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,12]]}},"alternative-id":["406"],"URL":"https:\/\/doi.org\/10.1007\/s42484-026-00406-4","relation":{},"ISSN":["2524-4906","2524-4914"],"issn-type":[{"value":"2524-4906","type":"print"},{"value":"2524-4914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,19]]},"assertion":[{"value":"18 July 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 June 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}},{"value":"Not applicable.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval and Consent to Participate"}},{"value":"All authors consent to the publication of this work.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for Publication"}},{"value":"Not applicable.","order":6,"name":"Ethics","group":{"name":"EthicsHeading","label":"Materials Availability"}}],"article-number":"68"}}