Before revision:  We study the quantum query complexity of computing the edge connectivity of a simple graph with n vertices and m edges in both the adjacency matrix and adjacency array models. For classical randomized algorithms,\tilde \tau) queries and time.
After revision:  We study the quantum query and time complexity of the minimum cut problem in the adjacency matrix model. If G has n vertices and edge weights at least 1 and at most \tau, we give a quantum algorithm to solve the minimum cut problem using\tilde \tau) queries and time.