Along their long propagation from production to detection, neutrino states undergo quantum interference which converts their types, or flavours. High-energy astrophysical neutrinos, first observed by the IceCube Neutrino Observatory, are known to propagate unperturbed over a billion light years in vacuum. These neutrinos act as the largest quantum interferometer and are sensitive to the smallest effects in vacuum due to new physics. Quantum gravity (QG) aims to describe gravity in a quantum mechanical framework, unifying matter, forces and space-time. QG effects are expected to appear at the ultra-high-energy scale known as the Planck energy, $E_{P}≡ 1.22\times 10^{19}$~giga-electronvolts (GeV). Such a high-energy universe would have existed only right after the Big Bang and it is inaccessible by human technologies. On the other hand, it is speculated that the effects of QG may exist in our low-energy vacuum, but are suppressed by the Planck energy as $E_{P}^{-1}$ ($∼ 10^{-19}$~GeV$^{-1}$), $E_{P}^{-2}$ ($∼ 10^{-38}$~GeV$^{-2}$), or its higher powers. The coupling of particles to these effects is too small to measure in kinematic observables, but the phase shift of neutrino waves could cause observable flavour conversions. Here, we report the first result of neutrino interferometry~\cite{Aartsen:2017ibm} using astrophysical neutrino flavours to search for new space-time structure. We did not find any evidence of anomalous flavour conversion in IceCube astrophysical neutrino flavour data. We place the most stringent limits of any known technologies, down to $10^{-42}$~GeV$^{-2}$, on the dimension-six operators that parameterize the space-time defects for preferred astrophysical production scenarios. For the first time, we unambiguously reach the signal region of quantum-gravity-motivated physics.