Q1 [open] Open Problem: "Determine the query complexity of learning quantum circuits with VIQs." (value injection queries, in the model of Section 1: unknown size-k quantum circuit on n qubits with gate order masked by an unknown permutation sigma; a VIQ is a tuple (x, S, (v_i in {0,1}^3 : i in S)) whose response is the measurement of the first n qubits after injecting each value v_i into gate sigma(i); lea
Q1a [open] Table 1, row VIQ, column 'with measurements': query complexity of learning quantum circuits with (measured) value injection queries - marked "open (fails test-path lemma)"; Lemma 2 shows the test-path approach of Angluin et al. (2009a) fails: "There is a circuit on which every (measured) VIQ leaving a path free makes the last output qubit uniformly random, yet with no VIQ the last output qubit is
Q1b [open] Table 1, row VIQ, column 'observing full state vector': query complexity of learning quantum circuits with value injection queries in the unmeasured variant ("We define the analogous unmeasured variant as well") - marked "open".