Hidden linear function problem (original) (raw)
The hidden linear function problem, is a search problem that generalizes the Bernstein–Vazirani problem. In the Bernstein–Vazirani problem, the hidden function is implicitly specified in an oracle; while in the 2D hidden linear function problem (2D HLF), the hidden function is explicitly specified by a matrix and a binary vector. 2D HLF can be solved exactly by a constant-depth quantum circuit restricted to a 2-dimensional grid of qubits using bounded fan-in gates but can't be solved by any sub-exponential size, constant-depth classical circuit using unbounded fan-in AND, OR, and NOT gates.While Bernstein–Vazirani's problem was designed to prove an oracle separation between complexity classes BQP and BPP, 2D HLF was designed to prove an explicit separation between the circuit classes and
| Property | Value |
|---|---|
| dbo:abstract | The hidden linear function problem, is a search problem that generalizes the Bernstein–Vazirani problem. In the Bernstein–Vazirani problem, the hidden function is implicitly specified in an oracle; while in the 2D hidden linear function problem (2D HLF), the hidden function is explicitly specified by a matrix and a binary vector. 2D HLF can be solved exactly by a constant-depth quantum circuit restricted to a 2-dimensional grid of qubits using bounded fan-in gates but can't be solved by any sub-exponential size, constant-depth classical circuit using unbounded fan-in AND, OR, and NOT gates.While Bernstein–Vazirani's problem was designed to prove an oracle separation between complexity classes BQP and BPP, 2D HLF was designed to prove an explicit separation between the circuit classes and. (en) |
| dbo:wikiPageExternalLink | https://github.com/quantumlib/Cirq/blob/master/docs/tutorials/hidden_linear_function.ipynb |
| dbo:wikiPageID | 63840940 (xsd:integer) |
| dbo:wikiPageLength | 4221 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1030136043 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quantum_logic_gate dbr:NOT_gate dbr:OR_gate dbr:Oracle dbr:NC_(complexity) dbr:Bernstein–Vazirani_algorithm dbr:Complexity_class dbr:BPP_(complexity) dbr:BQP dbc:Quantum_algorithms dbr:Fan-in dbr:Hadamard_gate dbr:AND_gate dbc:Quantum_complexity_theory dbc:Computational_complexity_theory dbr:Bit_array dbr:Search_problem dbr:Quantum_circuit dbr:Triangular_matrix dbr:Binary_matrix |
| dbp:cs1Dates | y (en) |
| dbp:date | June 2020 (en) |
| dbp:wikiPageUsesTemplate | dbt:Reflist dbt:Use_dmy_dates dbt:Quantum_computing |
| dct:subject | dbc:Quantum_algorithms dbc:Quantum_complexity_theory dbc:Computational_complexity_theory |
| rdfs:comment | The hidden linear function problem, is a search problem that generalizes the Bernstein–Vazirani problem. In the Bernstein–Vazirani problem, the hidden function is implicitly specified in an oracle; while in the 2D hidden linear function problem (2D HLF), the hidden function is explicitly specified by a matrix and a binary vector. 2D HLF can be solved exactly by a constant-depth quantum circuit restricted to a 2-dimensional grid of qubits using bounded fan-in gates but can't be solved by any sub-exponential size, constant-depth classical circuit using unbounded fan-in AND, OR, and NOT gates.While Bernstein–Vazirani's problem was designed to prove an oracle separation between complexity classes BQP and BPP, 2D HLF was designed to prove an explicit separation between the circuit classes and (en) |
| rdfs:label | Hidden linear function problem (en) |
| owl:sameAs | wikidata:Hidden linear function problem https://global.dbpedia.org/id/CmQF5 |
| prov:wasDerivedFrom | wikipedia-en:Hidden_linear_function_problem?oldid=1030136043&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Hidden_linear_function_problem |
| is dbo:wikiPageRedirects of | dbr:Hidden_Linear_Function_problem |
| is dbo:wikiPageWikiLink of | dbr:Hidden_Linear_Function_problem |
| is foaf:primaryTopic of | wikipedia-en:Hidden_linear_function_problem |