{"id":"W4235140742","doi":"10.26421/qic14.5-6-8","title":"Hardness of approximation for quantum problems","year":2014,"lang":"en","type":"article","venue":"Quantum Information and Computation","topic":"Quantum Computing Algorithms and Architecture","field":"Computer Science","cited_by":3,"is_retracted":false,"has_abstract":true,"ca_institutions":"","funders":"Natural Sciences and Engineering Research Council of Canada; Wolfson Family Charitable Trust; University of Waterloo; Agence Nationale de la Recherche","keywords":"Hierarchy; Mathematics; Hardness of approximation; Polynomial hierarchy; Quantum; Hamiltonian (control theory); Generalization; Quantum complexity theory; Set cover problem; Quantum algorithm; Polynomial; Discrete mathematics; Approximation algorithm; Combinatorics; Time complexity; Set (abstract data type); Quantum mechanics; Computer science; Mathematical optimization; Physics; Mathematical analysis","routes":{"ca_aff":false,"ca_fund":true,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":true},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.002971777,0.0007644165,0.001777101,0.001423104,0.002297081,0.004655143,0.002926368,0.002890197,0.00671978],"category_scores_gemma":[0.02090975,0.0006353153,0.002281211,0.001776814,0.004784293,0.01262016,0.004524244,0.008132686,0.0005703043],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.004651144,"about_ca_system_score_gemma":0.002329026,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.002875498,"about_ca_topic_score_gemma":0.001895132,"domain_scores_codex":[0.994204,0.001522737,0.0002697294,0.00112661,0.002066593,0.0008103786],"domain_scores_gemma":[0.975566,0.01936106,0.0007752099,0.002852394,0.0008541073,0.0005912469],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.0001640624,0.0001172406,0.0009779305,0.000337247,0.00006618445,0.00009135752,0.000553361,0.041886,0.001483244,0.9284959,0.005599292,0.02022823],"study_design_scores_gemma":[0.00002763228,0.00002453354,0.0004611095,0.00002695708,0.00001424951,0.00007597111,0.0001071992,0.09627405,0.0007719041,0.8993593,0.002839272,0.00001779554],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.2478747,0.002931782,0.6785828,0.01777675,0.0002577173,0.0002463971,0.001611971,0.00075539,0.04996243],"genre_scores_gemma":[0.9232283,0.001658526,0.06165976,0.001111821,0.0006597217,0.0002597505,0.001418893,0.0002289352,0.009774434],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.00671978,"threshold_uncertainty_score":0.0337466,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.01172081841731086,"score_gpt":0.2361089318281895,"score_spread":0.2243881134108786,"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."}}