I read a quote once that said “Simple bacteria can divide about every 20 minutes and have many hundreds of different proteins, each containing 20 types of amino acids arranged in chains that might be several hundred long. For bacteria to evolve by beneficial mutations one at a time would take much, much longer than three or four billion years, the time that many scientists believe life has existed on earth.” I haven't performed the math to back up the quote. As well would it change the time required if the bacteria mutate in parallel rather than in series?

It's the "one at a time" that is the issue here. Evolution is a massively parallel process. If a beneficial mutation happens once every million gnerations, and a generation is 20 minutes, that's a beneficial mutation every 38 years. If you have a million cells, that's a beneficial mutation every 20 minutes. If you have a billion cells, that's 1000 beneficial mutations every 20 minutes. In your body there are around 40 trillion cells. There are something like 10^31 cells on earth.

It's called the plasmid exchange. The search is parallelized to however many individuals there are, which is arbitrarily large, then the result is shared.