idea: Exploring an O(n) Depth Operator (Position-Pro) for Quantum Permutations

[Yusheng-Hu]

[Discussion] Exploring an O(n) Depth Operator (Position-Pro) for Quantum Permutations

The Concept

Most quantum permutation implementations rely on general-purpose sorting networks with $O(n \log^2 n)$ depth. I’ve been exploring a Position-Pro (PP) approach that utilizes Factoradic-based addressing to drive swaps. The goal is to reduce circuit depth to a hardware-native $O(n)$.

Preliminary Results (N=5 TSP)

• Logic: Mapping permutations through a structured sequence of $n-1$ layers.
• Resource Cost: In a 5-city TSP test, the operator encoded the optimal route (distance 75) using only 12 CNOTs.
• Initial Observation: This low-depth structure seems promising for preserving coherence in the NISQ era.

Questions for the Community

1. Overhead Trade-off: Does the complexity of preparing the Factoradic control register negate the $O(n)$ gains of the operator itself?
2. Hardware Topology: How efficiently does this linear swap chain map onto non-linear physical topologies (e.g., Heavy-Hex or Grid)?
3. Scalability: For $n > 10$, are there hidden systematic errors or bottlenecks I might be overlooking?

I would appreciate any critical feedback or pointers to existing research on similar linear-depth permutation logic.

[Yusheng-Hu]

Why Quantum Computing May Have No Future in Permutations and TSP Problems?

1. The Fatal Flaw of Logical Generation Paths

Current quantum permutation schemes, even those employing the theoretically optimal PP (Position-Pure) Algorithm, are locked at a complexity of $O(n)$ depth. Given that the essence of permutation is the precise displacement of discrete positions, this Sequential Dependency is fatal for quantum hardware. In multi-qubit scenarios where $n > 2$, every logical step forward allows latency to severely erode decoherence. Consequently, attempting to construct permutations via sequential logic has no engineering future.

2. Chain Impact on Complex Problems (e.g., TSP)

If the construction of underlying permutation operators cannot escape the cost of sequential time, complex problems like TSP (Traveling Salesman Problem)—which rely on searching through permutation paths—cannot achieve true physical acceleration on quantum architectures. Most current "acceleration" schemes rely on fuzzy physical simulations (such as quantum annealing), which fail to provide the precise, discrete, and optimal deterministic results required.

3. The Only "Escape Hatch" — Native Operator

The sole possibility for quantum computing in the field of permutations lies in completely abandoning the "sequential computing" mindset and pursuing "Native Permutation". This means bypassing step-by-step swap logic and instead seeking a physical field capable of instantaneous multi-body interaction. Such a mechanism would allow the system to map directly from an initial state to the target permutation state with $O(1)$ depth.

4. Final Conclusion

Unless a paradigm shift from "logical programs" to "native physical operators" can be achieved, the precise generation of permutations will forever remain the domain of digital circuits like FPGAs/ASICs, which can perfectly master deterministic timing, rather than qubits.