Quantum communication is the interdisciplinary science of quantum mechanics and telecommunication theory. It has advantages of perfect information security and high efficiency in transmission. In recent years, the theoretical and experimental results show that quantum communication systems have the superiority over the traditional communication systems. Quantum communication systems are hopeful for solving the information security problems that everyone is facing today, therefore, they possess broad application prospects and are forming a research hotspot of the telecommunications field currently. On the other hand, Voice over Internet Protocol (VoIP) is the method to transmit the digitized packet voice in Internet around the world. The advantages of VoIP are that it can carry voice, data, video, telephone conference, electronic commerce, and electronic mail economically. VoIP can realize the information storage and retransmission easily and flexibly. However, VoIP also encounters the problem of information security. We are trying to combine the quantum communications network and the VoIP system together and build a brand new network named quantum VoIP network which combines the advantages of both quantum communications and VoIP. The data packets may be delayed and lost in a queue up with a router due to the congestion and link failure during the transmission of quantum information. In order to ensure the performance of quantum VoIP system, the routing optimization strategies are proposed in the paper. The relay technology based on entanglement swapping is adopted. The multiuse quantum communications are realized by giving priority to the quantum channels with the least relay nodes. Theoretical analysis and simulation results show that when the data transmission links are fail to work properly and routers are in congestion, adopting the routing optimization strategies in M/M/m queuing system with the bit error rate (BER) of quantum bit setting to be 0.2 and the number of common channels increasing from 4 to 8,, the percentage of call failure in quantum communication network decreases from 0.25 to 0.024, and the maximum throughput of quantum networks increases from 64 kbps to 132 kbps. In comparison, when the number of common channels is set to be 4 andthe BER of the quantum bit is from 0.3 to 0.1, the maximum throughput of quantum networks increases from 41 kbps to 140 kbps. Thus it can be concluded that the routing optimization strategies proposed in this paper can improve the performance of quantum VoIP system significantly.