What should we add?

There are several synthesis algorithms for linear nearest neighbor (LNN) connectivity (that can be embedded into heavy-hex connectivity). These algorithms include:

• Linear (CX) circuits with depth 5n (Kutin et al) Adding linear synthesis algorithm for LNN #9098
• Permutations with depth 3n (Kutin et al) Adding permutation synthesis algorithm for LNN #9082
• CZ circuits with 2q depth 2n+2 (Maslov et al) Synthesis of CZ and Clifford circuits for linear nearest neighbor connectivity #9450
• Clifford circuits synthesis by layers (Bravyi and Maslov) Synthesis of a Clifford circuit into layers #9220
• CX-CZ circuits with 2q depth 5n (Maslov and Yang) & Clifford synthesis in 2q depth 7n-4 Adding depth-5n synthesis algorithm for -CZ-CX- circuits #9932
• StabilizerState synthesis requires only the layers H2 - S1 - CZ1 - H1 - so it has 2q depth 2n+2 (depends on Add an equiv method to the StabilizerState class #9543)
• QFT circuits (Fowler et al, Fig 2.b from https://arxiv.org/abs/quant-ph/0402196 ) QFT circuit synthesis for linear nearest neighbor connectivity #11236
• Reverse permutations in depth 2n+2 (Kutin et al, Section 5, See QFT LNN code) Add reverse permutation for LNN connectivity #12181

These algorithms should be added to qiskit.synthesis.

For completeness, it would be useful to transfer Clifford and CNOT-Dihedral synthesis from qiskit.quantum_info.synthesis to qiskit.synthesis.

Further advanced synthesis methods could be added to qiskit ecosystem, and used via the High Level Synthesis plugin, such as the ones suggested in:
#8548 (comment)
#8769