{"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":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.002278223,0.0002783651,0.0004081711,0.0007752622,0.0002841114,0.0001938099,0.001949975,0.00007894332,0.000006891946],"category_scores_gemma":[0.00008808424,0.0002269233,0.00008226978,0.00223624,0.0005968265,0.0005131864,0.0007586308,0.0002456955,0.000008406351],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00008506522,"about_ca_system_score_gemma":0.000355801,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.0001217482,"about_ca_topic_score_gemma":0.00003212366,"domain_scores_codex":[0.9966618,0.0001023468,0.0007092345,0.0008042592,0.001113722,0.0006086213],"domain_scores_gemma":[0.9971871,0.001024343,0.0003083451,0.0008314095,0.0004344202,0.0002143345],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"design_other","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.0006572689,0.004355492,0.003653825,0.0002330699,0.0001368676,0.0001627172,0.03153083,0.238046,0.02980646,0.214101,0.001704724,0.4756118],"study_design_scores_gemma":[0.0008569207,0.002381996,0.02638859,0.000220273,0.000005935938,0.00004426032,0.00001538215,0.9630939,0.004808755,0.001332262,0.000523661,0.000328048],"study_design_candidate":"simulation_or_modeling","study_design_consensus":null,"genre_codex":"empirical","genre_gemma":"empirical","genre_scores_codex":[0.7399383,0.000007393111,0.2562204,0.00267218,0.0005045748,0.0003445715,0.00002122513,0.00009289802,0.0001984612],"genre_scores_gemma":[0.9177463,0.000004549787,0.08126766,0.0008238076,0.00009285679,0.000003438364,0.000003573386,0.00001159666,0.0000462059],"genre_candidate":"empirical","genre_consensus":"empirical","teacher_disagreement_score":0.7250479,"threshold_uncertainty_score":0.9253665,"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."}}