A geometric approach to quantum circuit lower bounds

What is the minimal size quantum circuit required to exactly implement a specified n-qubit unitary operation, U, without the use of ancilla qubits? We show that a lower bound on the minimal size is provided by the length of the minimal geodesic between U and the identity, I, where length is defined by a suitable Finsler metric on the manifold SU(2(n)). The geodesic curves on these manifolds have the striking property that once an initial position and velocity are set, the remainder of the geodesic is completely determined by a second order differential equation known as the geodesic equation. This is in contrast with the usual case in circuit design, either classical or quantum, where being given part of an optimal circuit does not obviously assist in the design of the rest of the circuit. Geodesic analysis thus offers a potentially powerful approach to the problem of proving quantum circuit lower bounds. In this paper we construct several Finsler metrics whose minimal length geodesics provide lower bounds on quantum circuit size. For each Finsler metric we give a procedure to compute the corresponding geodesic equation. We also construct a large class of solutions to the geodesic equation, which we call Pauli geodesics, since they arise from isometries generated by the Pauli group. For any unitary U diagonal in the computational basis, we show that: (a) provided the minimal length geodesic is unique, it must be a Pauli geodesic; (b) finding the length of the minimal Pauli geodesic passing from I to U is equivalent to solving an exponential size instance of the closest vector in a lattice problem (CVP); and (c) all but a doubly exponentially small fraction of such unitaries have minimal Pauli geodesics of exponential length.

A novel phantom and method for comprehensive 3-dimensional measurement and correction of geometric distortion in magnetic resonance imaging

A phantom that can be used for mapping geometric distortion in magnetic resonance imaging (MRI) is described. This phantom provides an array of densely distributed control points in three-dimensional (3D) space. These points form the basis of a comprehensive measurement method to correct for geometric distortion in MR images arising principally from gradient field non-linearity and magnet field inhomogeneity. The phantom was designed based on the concept that a point in space can be defined using three orthogonal planes. This novel design approach allows for as many control points as desired. Employing this novel design, a highly accurate method has been developed that enables the positions of the control points to be measured to sub-voxel accuracy. The phantom described in this paper was constructed to fit into a body coil of a MRI scanner, (external dimensions of the phantom were: 310 mm x 310 mm x 310 mm), and it contained 10,830 control points. With this phantom, the mean errors in the measured coordinates of the control points were on the order of 0.1 mm or less, which were less than one tenth of the voxel's dimensions of the phantom image. The calculated three-dimensional distortion map, i.e., the differences between the image positions and true positions of the control points, can then be used to compensate for geometric distortion for a full image restoration. It is anticipated that this novel method will have an impact on the applicability of MRI in both clinical and research settings. especially in areas where geometric accuracy is highly required, such as in MR neuro-imaging. (C) 2004 Elsevier Inc. All rights reserved.

Geometric distortion in clinical MRI systems - Part I: evaluation using a 3D phantom

Recently, a 3D phantom that can provide a comprehensive and accurate measurement of the geometric distortion in MRI has been developed. Using this phantom, a full assessment of the geometric distortion in a number of clinical MRI systems (GE and Siemens) has been carried out and detailed results are presented in this paper. As expected, the main source of geometric distortion in modern superconducting MRI systems arises from the gradient field nonlinearity. Significantly large distortions with maximum absolute geometric errors ranged between 10 and 25 mm within a volume of 240 x 240 x 240 mm(3) were observed when imaging with the new generation of gradient systems that employs shorter coils. By comparison, the geometric distortion was much less in the older-generation gradient systems. With the vendor's correction method, the geometric distortion measured was significantly reduced but only within the plane in which these 2D correction methods were applied. Distortion along the axis normal to the plane was, as expected, virtually unchanged. Two-dimensional correction methods are a convenient approach and in principle they are the only methods that can be applied to correct geometric distortion in a single slice or in multiple noncontiguous slices. However, these methods only provide an incomplete solution to the problem and their value can be significantly reduced if the distortion along the normal of the correction plane is not small. (C) 2004 Elsevier Inc. All rights reserved.