Lab Home | Phone | Search
	Center for Nonlinear Studies
	Home  ▶ People   CNLS Staff Members   Executive Committee   Postdocs   Visitors   Students   Research   Publications  ▶ Conferences   Workshops   Sponsorship  ▶ Talks   Seminars   Postdoc Seminars Archive   Quantum Lunch   Quantum Lunch Archive   P/T Colloquia   Archive   Ulam Scholar     Postdoc Nominations  ▶ Student Requests   Student Program  ▶ Visitor Requests   Description   Past Visitors  ▶ Services   General     History of CNLS     Maps, Directions   T-Division   LANL				Monday, June 16, 202510:30 AM - 11:30 AMCNLS Conference Room (TA-3, Bldg 1690) Seminar Efficient encodings for permutation-based problems Denny DahlIonQ Combinatorial optimization problems whose search space is a set of permutations introduce significant difficulty for quantum computation. The traditional approach to encoding apermutation is to represent the matrix elements of a permutation matrix using qubits. This results inan N**2 encoding for elements of the symmetric group over N elements. The group size grows asNlog(N), so valid states become a vanishingly small fraction of the entire search space as N grows. Efficient permutation encodings that only require Nlog(N) qubits can be constructed using sorting networks. Constructing the objective functions for permutation-based problems such as the Traveling Salesman Problem can be automated with symbolic logic. The resulting objective functions contain many higher order terms. Handling these with QAOA in the circuit model creates an opportunity to use heuristics for phase polynomials. Teams: Join the meeting now Meeting ID: 249 207 579 967 Passcode: 6GC6qy6B Host: Luis Pedro Garcia-Pintos (T-4)