Trong lý thuyết độ phức tạp tính toán và tính toán lượng tử, bài toán Simon là một bài toán thuộc dạng cây quyết định hay dạng truy vấn, được diễn tả bởi Daniel Simon năm 1994. Simon đã đưa ra một thuật toán lượng tử, thường được gọi là thuật toán Simon, để giải quyết bài toán nhanh hơn rất nhiều (một số mũ lần) so với bất kì thuật toán (xác định hay xác suất) cổ điển nào.Thuật toán Simon sử dụng O ( n ) {\displaystyle O(n)} truy vấn trong hộp đen, trong khi thuật toán xác suất cổ điển mạnh nhất cũng phải mất tối thiểu Ω ( 2 n / 2 ) {\displaystyle \Omega (2^{n/2})} truy vấn. Thuật toán Simon cũng được coi là tốt nhất, do bất kì thuật toán lượng tử nào để giải quyết bài toán này cũng cần tối thiểu Ω ( n ) {\displaystyle \Omega (n)} truy vấn. Bài toán này chỉ ra sự phân tách giữa BPP và BQP, không giống như của thuật toán Deutsch-Jozsa - phân tách P và EQP.Mặc dù bài toán thực ra có ít ứng dụng trong thực tế, tuy nhiên nó vẫn rất đáng được chú ý khi đã tạo ra một sự tăng tốc theo hàm mũ so với các thuật toán cổ điển. Thêm vào đó, đây cũng là cơ sở ý tưởng cho Thuật toán Shor. Cả hai bài toán đều là dạng đặc biệt của bài toán nhóm con ẩn giao hoán, là bài toán đến nay đã có thuật toán lượng tử để giải quyết một cách hiệu quả.