{"id":"W4231383310","doi":"10.1109/focs.2007.4389507","title":"Any AND-OR Formula of Size N can be Evaluated in time N^{1/2 + o(1)} on a Quantum Computer","year":2007,"lang":"en","type":"article","venue":"Annual Symposium on Foundations of Computer Science","topic":"Quantum Computing Algorithms and Architecture","field":"Computer Science","cited_by":19,"is_retracted":false,"has_abstract":true,"ca_institutions":"University of Waterloo","funders":"Army Research Office; Natural Sciences and Engineering Research Council of Canada; Latvijas Universitate; University of Waterloo; Mitacs; California Institute of Technology; Deutscher Akademischer Austauschdienst; National Science Foundation","keywords":"Quantum; Quantum computer; Computer science; Physics; Quantum mechanics","routes":{"ca_aff":true,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.002688572,0.001091918,0.00146022,0.0005201822,0.0012807,0.00331619,0.003014664,0.001850263,0.01758892],"category_scores_gemma":[0.0150328,0.0005383224,0.001689002,0.001337884,0.002092172,0.01136389,0.00285444,0.002426502,0.003114603],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002689339,"about_ca_system_score_gemma":0.004653062,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002347176,"about_ca_topic_score_gemma":0.005753753,"domain_scores_codex":[0.9963499,0.0007082532,0.0002592389,0.000881227,0.001050918,0.0007503745],"domain_scores_gemma":[0.9863551,0.009295065,0.0006897158,0.002716215,0.0006097804,0.0003340575],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.005884187,0.0007743586,0.005552131,0.001846913,0.0003504996,0.0004964897,0.0004957613,0.09569284,0.05951273,0.3890537,0.03998596,0.4003544],"study_design_scores_gemma":[0.0005648067,0.0003281856,0.002041588,0.0002015751,0.0002684805,0.0004373722,0.0002332081,0.3081996,0.03109872,0.6354868,0.02103263,0.0001069737],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2315767,0.002368826,0.657899,0.01530545,0.0005853583,0.0006265615,0.002533534,0.0070199,0.08208469],"genre_scores_gemma":[0.6662927,0.00147629,0.304149,0.00206298,0.0005679026,0.0007019043,0.002246919,0.0008691705,0.02163309],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01758892,"threshold_uncertainty_score":0.05884075,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01290182047010125,"score_gpt":0.2818570957638533,"score_spread":0.2689552752937521,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}