Abstract: A Quantum probability Coding Genetic Algorithm-QCGA is proposed, which is different from classical GAs. In QCGA, single individual represents a probability distribution of solutions, which covers the whole solution space. Individuals in QCGA evolve independently and in parallel. A new crossover operator is designed to implement the information exchange among individuals. A new mutation operator is also design to prevent the algorithm from falling into local optima. To study the efficiency and advantage of QCGA, the algorithm is applied to solve function optimization problems, knapsack problems, and to discover frequent structures from time series. Experimental results show that QCGA has good ability of global optimization, and good ability of diversity reservation, which makes it efficient for complex optimization problems.