Permanent vs Determinant
An exploratory study on matrix computations with applications in quantum computing and graph theory.
Project Overview
This research project explores the computational differences between matrix permanents and determinants, with a focus on their applications in quantum computing and graph theory. While determinants can be computed in polynomial time, calculating the permanent of a matrix is known to be #P-complete, making it significantly more challenging.
The permanent of a matrix plays a crucial role in quantum computing, particularly in linear optical quantum computing protocols where it represents the probability amplitudes of certain quantum states. In graph theory, permanents count the number of perfect matchings in bipartite graphs, providing valuable insights into network structures.
Time complexity comparison between determinant (polynomial) and permanent (exponential) calculations
This project implements various algorithms for approximating matrix permanents, compares their performance, and explores applications in quantum circuit simulation and graph analysis.
Key Algorithms Implemented
Ryser's Algorithm
An exact algorithm that computes the permanent in O(n·2ⁿ) time, significantly faster than the naive O(n!) approach but still exponential.
Jerrum-Sinclair-Vigoda
A fully polynomial randomized approximation scheme (FPRAS) for the permanent of matrices with non-negative entries.
Barvinok's Approximation
A polynomial-time algorithm that provides an εn-approximation for the permanent.
Gurvits' Scaling Algorithm
A deterministic approximation algorithm for the permanent of doubly stochastic matrices.
Theoretical Results
Complexity Analysis
We provide a rigorous analysis of the computational complexity gap between determinants and permanents, demonstrating why the latter remains intractable for large matrices despite various approximation techniques.
Error Bounds
We derive new error bounds for permanent approximation algorithms, especially for matrices arising in quantum computing applications, improving on previously known results by a factor of log(n).
Quantum Advantage
We establish conditions under which quantum computers can provide polynomial speedups for certain classes of permanent computations, with implications for sampling-based quantum supremacy experiments.
Applications
Quantum Computing
Implementation of Boson Sampling simulators using our optimized permanent algorithms, achieving state-of-the-art performance for systems with up to 30 photons.
Graph Theory
Analysis of perfect matchings in large bipartite networks, with applications to resource allocation problems in distributed systems.
Cryptography
Development of cryptographic schemes based on the hardness of computing permanents, potentially resistant to quantum attacks.
A bipartite graph where the permanent of its adjacency matrix counts the number of perfect matchings.
Mathematical Formulation
The permanent of an n×n matrix A is defined as:
where \( S_n \) is the symmetric group on n elements.
In contrast, the determinant is defined as:
where \( \text{sgn}(\sigma) \) is the sign of the permutation.
The computational difference arises from the sign term, which allows for efficient algorithms for determinants (like Gaussian elimination) but not for permanents.