The Monsoon trade-wind sea-route was known before the brith of Christ, so it wasn't too hard to sail from the horn of Africa to the west coast of India. So all the ingredients are there for Romans to travel to China and Chinese to travel to Rome.
I don't know if I can believe that intact units of Romans were fighting the Chinese in the Persian army though, that might be pushing it.