  Recently, a standardized framework was proposed for introducing
quantum-inspired moves in mathematical games with perfect information and no
chance. The beauty of quantum games-succinct in representation, rich in
structures, explosive in complexity, dazzling for visualization, and
sophisticated for strategic reasoning-has drawn us to play concrete games full
of subtleties and to characterize abstract properties pertinent to complexity
consequence. Going beyond individual games, we explore the tractability of
quantum combinatorial games as whole, and address fundamental questions
including:
  Quantum Leap in Complexity: Are there polynomial-time solvable games whose
quantum extensions are intractable?
  Quantum Collapses in Complexity: Are there PSPACE-complete games whose
quantum extensions fall to the lower levels of the polynomial-time hierarchy?
  Quantumness Matters: How do outcome classes and strategies change under
quantum moves? Under what conditions doesn't quantumness matter?
  PSPACE Barrier for Quantum Leap: Can quantum moves launch PSPACE games into
outer polynomial space
  We show that quantum moves not only enrich the game structure, but also
impact their computational complexity. In settling some of these basic
questions, we characterize both the powers and limitations of quantum moves as
well as the superposition of game configurations that they create. Our
constructive proofs-both on the leap of complexity in concrete Quantum Nim and
Quantum Undirected Geography and on the continuous collapses, in the quantum
setting, of complexity in abstract PSPACE-complete games to each level of the
polynomial-time hierarchy-illustrate the striking computational landscape over
quantum games and highlight surprising turns with unexpected quantum impact.
Our studies also enable us to identify several elegant open questions
fundamental to quantum combinatorial game theory (QCGT).
