La secuencia más corta de puertas cuánticas universales que corresponden a un unitario dado

Pregunta: Dada una matriz unitaria que actúa sobre qubits, ¿podemos encontrar la secuencia más corta de puertas Clifford + T que correspondan a esa unidad?$n$

Para antecedentes sobre la cuestión, dos referencias importantes:

1. Síntesis exacta rápida y eficiente de unidades de un solo qubit generadas por Clifford y puertas T por Kliuchnikov, Maslov y Mosca
2. Síntesis exacta de circuitos Clifford + T multiqubit por Giles y Selinger.

Conseguir una descomposición óptima es definitivamente un problema abierto. (Y, por supuesto, la descomposición es intratable, compuertas para n grande .) Una pregunta "más simple" que podría hacer primero es cuál es la secuencia más corta de cnots y rotaciones de qubit único por cualquier ángulo, (qué IBM, Rigetti, y pronto Google ofrece actualmente, esta base universal de puertas se puede expresar en términos de su base de Cliffords y puertas t). Esta pregunta "más simple" también está abierta y tiene una respuesta no única. Una pregunta relacionada es qué es una descomposición óptima exacta de las compuertas desde una base universal para pasar del estado fundamental a un estado final dado.$\exp(n)$$n$

Supongo que se refiere a descomposiciones exactas. Si desea descomposiciones aproximadas, existen diferentes métodos para eso, como la descomposición Trotter-Suzuki, o aproximar una descomposición exacta.

El "compilador de csd cuántico" en Qubiter realiza una descomposición no optimizada de cualquier n qubit unitario en cnots y pudriciones qubit simples usando la famosa subrutina csd (descomposición coseno-seno) de LAPACK. Alguna persona emprendedora podría intentar encontrar optimizaciones para el compilador cuántico de Qubiter. ¡Puedes usar el compilador de Qubiter, por ejemplo (escribí un artículo sobre esto), para permitir que tu computadora clásica vuelva a descubrir la descomposición cuántica de la Transformada de Fourier de Coppersmith!

Qubiter es de código abierto y está disponible en github (divulgación completa - lo escribí).

Suponga que es posible una síntesis exacta para su unitario proporcionado (el número de restricciones teóricas en las entradas) y que los algoritmos descritos en la pregunta le dieron una secuencia de puertas Clifford + T que implementaron ese unitario. Como se indica en el documento de Giles-Selinger, obtienes una secuencia que está muy lejos de ser óptima. Entonces, en este punto, se ha reducido el problema verbal en el grupo generado por el conjunto de puertas Clifford + T. Algunos grupos tienen algoritmos para acortar una palabra dada mientras aún representan el mismo elemento del grupo en una forma normal que es la más corta dentro de esa clase. Otros no lo hacen.

$2$$S_1$$1$$CNOT_{12}$$1$$S_i^4=1$$X_i Y_j = Y_j X_i$$i \neq j$$S_1 S_1 S_2 S_1 S_1$$S_1 S_2 = S_2 S_1$$S_1^4=1$$S_2$como una palabra más corta que representa el mismo elemento de grupo. Para una presentación grupal dada, a uno le gustaría un algoritmo que tome una palabra arbitraria y la reduzca. En general esto no es posible.

Descargo de responsabilidad a continuación: Próximo proyecto / Implementación conjunta de Haskell con Jon Aytac.

$r_i$$(r_i r_j)^{m_{ij}}=1$. Ese es un grupo Coxeter relacionado con el conjunto de compuertas Clifford + T, pero con un problema de palabras eficientemente solucionable. Entonces, uno puede tomar el resultado del algoritmo de Giles-Selinger y potencialmente acortarlo usando solo estas relaciones muy simples (después de mirar segmentos con solo esas letras de involución). De hecho, cualquier algoritmo que tome un unitario dado y se aproxime o sintetice exactamente en Clifford + T puede introducirse en este procedimiento para acortarlo un poco.