tl;dr: No, but yes, depending on your background and who you talked to, and also where in the states you're from.

The answer is no, not likely, if you were speaking the language of Qin and they were speaking the language of Chu, but then it's also yes, if you were well educated, because actually a lot of people spoke the language of Qi/Zhou as the prestige language variety. So, you could probably get quite far speaking Qi/Zhou's language, at least in certain circles.

One problem in answering this is that we don't actually know what the spoken language would have been, exactly. We know bits of the major language groups, but of course we also should remember that there's not only going to be internal diversity but also the exact time you were to visit would matter, as the language landscape was changing.

We know spoken Chu was different from various other varieties, but Chu speakers also wrote in the Zhou/Qi style (again, as it was the prestige variety). And then precisely because were writing in the same style as Zhou, we are still given only hints in such texts where Chu is brought up as to what it might have been like.

Much of the modern attention on Qin language is primarily focused on writing, which is too bad. Like all states/regions, Chu has their own variations on a non-standard system, and while Qin is often credited with standardising it, that's not actually what happened. That's for another thread though. You can see examples of Chu writing on old gold plates which they are known for, if you're interested.

The Chu language is believed by some to have been a Sinitic language, related to Old Chinese. Others have felt strongly that it's not. Mei Tsu-Lin and Jerry Norman, both well regarded scholars in their own right, wrote on Austroasiatic (Mon–Khmer) features in Chu writings. It's possible that it was Sinitic, and it's possible it was Austroasiatic, and in either case borrowed heavily from languages belonging to the other family. Borrowing was incredibly common, and muddies the waters when we're trying to trace origins.

Chu's grammar in terms of word order was not the same as Sinitic languages, and is more in line with Austroasiatic. Lexical items were quite different as well.

So, Chu may have been Sinitic, but was likely Austroasiatic. Then there are also some who argue that Zhou was not speaking a Sinitic language either. Either way, what's clear is that a bunch of different language families were in use in the area at the time. Wu like Chu was probably Austroasiatic. Yue may have been Austronesian, or Mon-Khmer, or something else. I've posted here recently giving more on Wu and Chu and Yue, but really the jury is still out on exactly what they would have been.

What Qin spoke is also a bit of a mystery. There's a good chance they had substantial influence from Ba and Shu, which today survives as influences on Southwestern Mandarin, but about which we also don't have a lot of info. Ba-shu has the same problem as Chu; people weren't fully writing in it so we kinda only have hints. It's like finding one piece of a 100 piece puzzle and trying to work out what the whole picture may have been, but also being super familiar with puzzle tropes. That's a weird analogy, but screw it, I'm leaving it in.

I don't know a huge amount about Qin language. My personal interests lie further to the East. However just knowing the diversity of the region, and how many language families were there, and the significant distance between Qin and Chu cultural centres, and the fact that there was an alternate third option that people used for diplomatic purposes, it's unlikely that there would have been any great degree of mutual intelligibility between Qin and Chu, especially if we're talking further into the Warring States period when Chu and Wu and Yue had basically merged and cross-pollinated linguistically.

I think the Austroasiatic/Mon-Khmer hypothesis for Wu and Chu are likely, and then add that Yue is likely either Mon-Khmer, Austronesian or Hmong-Mien, and that it's highly unlike that Qin was any of those, I really don't think there's any reason to suspect they'd have any level of mutual intelligibility between the two state's prestige language varieties.

Of course, this all changes if you're from the border area of Qin close to Chu, in which case you likely would totally be able to understand people from the Chu side of the "border", because you're likely speaking something other than the prestige varieties anyway, and the chance that you're speaking something quite similar across the border is high.

See also:

• Dong 2014 A History of the Chinese Language

• Knechtges 2010 Ancient and Early Medieval Chinese Literature

• Sun Chaofen 2006 Chinese: A Linguistic Introduction