  Magic sets of observables are minimal structures that capture quantum
state-independent advantage for systems of $n\ge 2$ qubits and are, therefore,
fundamental tools for investigating the interface between classical and quantum
physics. A theorem by Arkhipov (arXiv:1209.3819) states that $n$-qubit magic
sets in which each observable is in exactly two subsets of compatible
observables can be reduced either to the two-qubit magic square or the
three-qubit magic pentagram [N. D. Mermin, Phys. Rev. Lett. 65, 3373 (1990)].
An open question is whether there are magic sets that cannot be reduced to the
square or the pentagram. If they exist, a second key question is whether they
require $n >3$ qubits, since, if this is the case, these magic sets would
capture minimal state independent quantum advantage that is specific for
$n$-qubit systems with specific values of $n$. Here, we answer both questions
affirmatively. We identify magic sets which cannot be reduced to the square or
the pentagram and require $n=3,4,5$, or $6$ qubits. In addition, we prove a
generalized version of Arkhipov's theorem providing an efficient algorithm for,
given a hypergraph, deciding whether or not it can accommodate a magic set, and
solve another open problem, namely, given a magic set, obtaining the tight
bound of its associated noncontextuality inequality.
