Điện toán lượng tử

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 8)

Điện toán lượng tử

Bernstein-Vazirani Quantum Algorithm

Thời gian (Time) O(1)
Không gian (Space) O(Qubits)

Mô tả nguyên lý

Tìm chuỗi bit ẩn s trong hàm số tuyến tính $f(x) = s \cdot x \pmod 2$ với 1 lần truy vấn.

Cài đặt mẫu (Implementation)

// Áp dụng song song trạng thái chồng chập và phát hiện pha bit ẩn.
Điện toán lượng tử

Deutsch-Jozsa Quantum Algorithm

Thời gian (Time) O(1)
Không gian (Space) O(Qubits)

Mô tả nguyên lý

Phân biệt hàm số hằng (constant) và hàm số cân bằng (balanced) chỉ với 1 lần gọi hàm.

Cài đặt mẫu (Implementation)

// Tận dụng sự can thiệp lượng tử (quantum interference) qua cổng Hadamard.
Điện toán lượng tử

Grover Quantum Database Search

Thời gian (Time) O(sqrt(N))
Không gian (Space) O(Log N qubits)

Mô tả nguyên lý

Thuật toán tìm kiếm không có cấu trúc trên không gian N phần tử với tốc độ căn bậc hai.

Cài đặt mẫu (Implementation)

// Lặp lại toán tử khuếch đại biên độ (amplitude amplification) qua các cổng lượng tử.
Điện toán lượng tử

Quantum Amplitude Amplification

Thời gian (Time) O(sqrt(N))
Không gian (Space) O(Qubits)

Mô tả nguyên lý

Tổng quát hóa thuật toán Grover để khuếch đại biên độ xác suất của tập hợp trạng thái thỏa mãn.

Cài đặt mẫu (Implementation)

// Xoay vector trạng thái trong không gian con chứa nghiệm mong muốn.
Điện toán lượng tử

Quantum Fourier Transform (QFT)

Thời gian (Time) O((log N)^2)
Không gian (Space) O(Log N qubits)

Mô tả nguyên lý

Phiên bản lượng tử của biến đổi Fourier rời rạc, nền tảng của nhiều thuật toán lượng tử tối ưu.

Cài đặt mẫu (Implementation)

// Áp dụng chuỗi cổng Hadamard và cổng xoay pha có điều khiển (Controlled-Phase gates).
Điện toán lượng tử

Quantum Phase Estimation (QPE)

Thời gian (Time) O(t^2)
Không gian (Space) O(t qubits)

Mô tả nguyên lý

Ước lượng giá trị pha (eigenvalue) của toán tử đơn nhất (unitary operator) trên hệ lượng tử.

Cài đặt mẫu (Implementation)

// Kết hợp biến đổi QFT ngược và các phép điều khiển lũy thừa toán tử.
Điện toán lượng tử

Shor Integer Factorization Quantum Circuit

Thời gian (Time) O((log N)^3)
Không gian (Space) O(log N)

Mô tả nguyên lý

Thuật toán lượng tử tìm chu kỳ hàm số để phân tích thừa số nguyên tố với tốc độ hàm mũ.

Cài đặt mẫu (Implementation)

// Áp dụng biến đổi Fourier lượng tử (QFT) để tìm chu kỳ r của hàm số $a^x \pmod N$.
Điện toán lượng tử

Simon Period Finding Algorithm

Thời gian (Time) O(N)
Không gian (Space) O(Log N)

Mô tả nguyên lý

Tìm chu kỳ bit ẩn s trong hàm số thỏa mãn $f(x) = f(y) \iff x \oplus y \in \{0, s\}$.

Cài đặt mẫu (Implementation)

// Thu thập các phương trình tuyến tính qua đo đạc lượng tử và giải hệ qua trường F2.