Patent Publication Number: US-11042812-B2

Title: Optimized testing of quantum-logic circuits

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application is a continuation application claiming priority to Ser. No. 16/014,117 filed Jun. 21, 2018, now U.S. Pat. No. 10,393,807 issued Aug. 27, 2019, which is a continuation application claiming priority to Ser. No. 15/194,645, filed Jun. 28, 2016 now U.S. Pat. No. 10,082,539 issued Sep. 25, 2018, the contents of which are hereby incorporated by reference. 
    
    
     TECHNICAL FIELD 
     The present invention relates to testing quantum-logic circuits and in particular to using direct-sum computations to test partially symmetric quantum-logic circuits. 
     BACKGROUND 
     Unlike conventional binary logic, quantum logic is not limited to binary states of 0 and 1. Inputs and outputs of quantum-logic circuits may thus assume far more states than analogous binary-logic circuits, greatly increasing the number of tests that may be performed upon a quantum-logic circuit (or “q-module”) to verify correct operation. Testing a q-module comprising larger numbers of inputs and states can therefore be prohibitively expensive or resource-intensive. 
     BRIEF SUMMARY 
     A first embodiment of the present invention provides a quantum-logic test-development system comprising a processor, a memory coupled to the processor, and a computer-readable hardware storage device coupled to the processor, the storage device containing program code configured to be run by the processor via the memory to implement a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits, the method comprising: 
     the system receiving architectural information about a quantum-logic circuit that has at least four inputs and at least one output; 
     the system, as a function of the architectural information, dividing the at least four inputs into two or more non-intersecting subsets; 
     the system creating a set of groups that each comprise a subset, selected from the set of two or more non-intersecting subsets, and one or more permutation operations capable of being performed upon inputs comprised by the selected subset; 
     the system generating a direct sum of the set of groups, 
     where the direct sum identifies an invariance group of a function that represents functionality of the quantum-logic circuit, 
     where the invariance group comprises a set of invariant permutations, 
     where each permutation of the set of invariant permutations identifies a permutation of two or more inputs comprised by one and only one subset of the two or more non-intersecting subsets, and 
     where no output of the quantum-logic circuit changes state when any permutation of the set of invariant permutations is performed upon the at least four inputs of the quantum-logic circuit. 
     A second embodiment of the present invention provides method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits, the method comprising: 
     receiving architectural information about a quantum-logic circuit that has at least four inputs and at least one output; 
     dividing the at least four inputs, as a function of the architectural information, into two or more non-intersecting subsets; 
     creating a set of groups that each comprise a subset, selected from the set of two or more non-intersecting subsets, and one or more permutation operations capable of being performed upon inputs comprised by the selected subset; 
     generating a direct sum of the set of groups, 
     where the direct sum identifies an invariance group of a function that represents functionality of the quantum-logic circuit, 
     where the invariance group comprises a set of invariant permutations, 
     where each permutation of the set of invariant permutations identifies a permutation of two or more inputs comprised by one and only one subset of the two or more non-intersecting subsets, and 
     where no output of the quantum-logic circuit changes state when any permutation of the set of invariant permutations is performed upon the at least four inputs of the quantum-logic circuit. 
     A third embodiment of the present invention provides a computer program product, comprising a computer-readable hardware storage device having a computer-readable program code stored therein, the program code configured to be executed by a quantum-logic test-development system comprising a processor, a memory coupled to the processor, and a computer-readable hardware storage device coupled to the processor, the storage device containing program code configured to be run by the processor via the memory to implement a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits, the method comprising: 
     receiving architectural information about a quantum-logic circuit that has at least four inputs and at least one output; 
     dividing the at least four inputs, as a function of the architectural information, into two or more non-intersecting subsets; 
     creating a set of groups that each comprise a subset, selected from the set of two or more non-intersecting subsets, and one or more permutation operations capable of being performed upon inputs comprised by the selected subset; 
     generating a direct sum of the set of groups, 
     where the direct sum identifies an invariance group of a function that represents functionality of the quantum-logic circuit, 
     where the invariance group comprises a set of invariant permutations, 
     where each permutation of the set of invariant permutations identifies a permutation of two or more inputs comprised by one and only one subset of the two or more non-intersecting subsets, and 
     where no output of the quantum-logic circuit changes state when any permutation of the set of invariant permutations is performed upon the at least four inputs of the quantum-logic circuit. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows the structure of a computer system and computer program code that may be used to implement a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits in accordance with embodiments of the present invention. 
         FIG. 2  is a flow chart that illustrates steps of a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits in accordance with embodiments of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     Embodiments of the present invention streamline the testing process for a class of quantum-logic circuits known as “partially symmetric” circuits. 
     Testing a quantum-logic circuit (or “q-module”) can be far more time-consuming and resource-intensive than testing conventional binary logic circuits because quantum logic is not limited to two states. Where verifying operation of a two-input binary AND circuit would require four tests, corresponding to four possible binary inputs {00, 01, 10, and 11}, a two-input q-module that supports four states A, B, C, and D, would require 16 tests to test 16 possible input states {AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, and DD}. Embodiments of the present invention solve this technical problem by enhancing the operation of a circuit-testing software application or a hardware circuit-testing device. 
     The number of necessary tests needed to verify a q-module increases as a geometric function of the circuit&#39;s number of states or number of inputs. In general, a circuit with n inputs and t states (t&gt;1) would require t n  tests in order to verify each possible set of input values. An n-input binary-logic circuit that supports only values of 0 and 1 would thus require only 2 n  tests. 
     In general, permuting any of a q-module&#39;s inputs causes its output to change. Consider, for example, a 3-input, 1-output q-module with inputs {x 1 , x 2 , x 3 }, each of which can be in any of four states {A, B, C, D}. The module&#39;s single output can be in any of three states {E, F, G}. The three inputs may be reordered into six possible permutations: (x 1 , x 2 , x 3 ), (x 1 , x 3 , x 2 ), (x 2 , x 1 , x 3 ), (x 2 , x 3 , x 1 ), (x 3 , x 1 , x 2 ), and (x 3 , x 2 , x 1 ). If inputs (x 1 , x 2 , x 3 ) are initially in states (A, B, C), permuting the order of two of those inputs to (x 1 , x 3 , x 2 ) would reorder the input states to (A, C, B). This permutation will in general cause the q-module&#39;s output to change. 
     A characteristic of some q-modules, however, is that certain permutations of the module&#39;s inputs never produce a change to the module&#39;s output state, regardless of the states of each input prior to permutation. If this is true of all possible permutations of all inputs, the circuit is said to be symmetrical. If it is true of only a proper subsets of all possible permutations of inputs, the circuit is said to be partially symmetrical. Note that nearly all q-modules are symmetric with respect to an identity permutation (id), which may consist of a permutation of 0 inputs. The identity permutation may be mentioned in examples and embodiments described in this document, but it should be considered a trivial case within the context of the present invention. 
     In the running example, the previously described 3-input, 1-output, 4-state quantum circuit may produce output E in response to receiving any input through inputs (x 1 , x 2 , x 3 ). After permuting the x 2  and x 3  inputs to reorder the q-module&#39;s inputs to (x 1 , x 3 , x 2 ), the circuit may still produce the same output E. Then, a permutation (2,3) (which swaps the second and third inputs x 2  and x 3 ) is said to be an element of a “Boolean function invariance group” or of a “symmetry group” of a function f( ) represented by the q-module, and the q-module itself is said to be “symmetric” under permutation (2,3). In this document, we will refer to function f( ) as f k ( x ), where  x  is an n-tuple vector representation (x 1 , . . . , x n ) of the q-module&#39;s n inputs. 
     One property of an invariance group is that the permutations contained by the group are invariant regardless of the initial states of the permuted inputs. In the above example, the one-permutation invariance group {(2,3)} specifies that permuting the q-module&#39;s second and third inputs never changes the module&#39;s output. So, for example, if the states of the inputs change from (ABA) to (AAB), from (CCB) to (CBC), or from (CBA) to (CAB), the output of the q-module does not change. 
     Embodiments of the present invention employ this concept of invariance groups to greatly reduce the number of input vectors  x  that must be tested in order fully verify a q-module. Because applying an invariant permutation to a q-module&#39;s input vector  x  is known to leave the q-module&#39;s output unchanged, once that initial vector  x  has been tested, any other vector that may be generated by applying the invariant permutation to  x  is automatically deemed to have been verified. When an invariance group of a partially symmetric q-module comprises a significant number of permutations, embodiments of the present invention may dramatically reduce the number of tests required to fully verify the circuit. 
       FIG. 1  shows a structure of a computer system and computer program code that may be used to implement a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits in accordance with embodiments of the present invention.  FIG. 1  refers to objects  101 - 115 . 
     Aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module,” or “system.” 
     The present invention may be a system, a method, and/or a computer program product at any possible technical detail level of integration. The computer program product may include a computer readable storage medium (or media) having computer readable program instructions thereon for causing a processor to carry out aspects of the present invention. 
     The computer readable storage medium can be a tangible device that can retain and store instructions for use by an instruction execution device. The computer readable storage medium may be, for example, but is not limited to, an electronic storage device, a magnetic storage device, an optical storage device, an electromagnetic storage device, a semiconductor storage device, or any suitable combination of the foregoing. A non-exhaustive list of more specific examples of the computer readable storage medium includes the following: a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or Flash memory), a static random access memory (SRAM), a portable compact disc read-only memory (CD-ROM), a digital versatile disk (DVD), a memory stick, a floppy disk, a mechanically encoded device such as punch-cards or raised structures in a groove having instructions recorded thereon, and any suitable combination of the foregoing. A computer readable storage medium, as used herein, is not to be construed as being transitory signals per se, such as radio waves or other freely propagating electromagnetic waves, electromagnetic waves propagating through a waveguide or other transmission media (e.g., light pulses passing through a fiber-optic cable), or electrical signals transmitted through a wire. 
     Computer readable program instructions described herein can be downloaded to respective computing/processing devices from a computer readable storage medium or to an external computer or external storage device via a network, for example, the Internet, a local area network, a wide area network and/or a wireless network. The network may comprise copper transmission cables, optical transmission fibers, wireless transmission, routers, firewalls, switches, gateway computers and/or edge servers. A network adapter card or network interface in each computing/processing device receives computer readable program instructions from the network and forwards the computer readable program instructions for storage in a computer readable storage medium within the respective computing/processing device. 
     Computer readable program instructions for carrying out operations of the present invention may be assembler instructions, instruction-set-architecture (ISA) instructions, machine instructions, machine dependent instructions, microcode, firmware instructions, state-setting data, configuration data for integrated circuitry, or either source code or object code written in any combination of one or more programming languages, including an object oriented programming language such as Smalltalk, C++, or the like, and procedural programming languages, such as the “C” programming language or similar programming languages. The computer readable program instructions may execute entirely on the user&#39;s computer, partly on the user&#39;s computer, as a stand-alone software package, partly on the user&#39;s computer and partly on a remote computer or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user&#39;s computer through any type of network, including a local area network (LAN) or a wide area network (WAN), or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider). In some embodiments, electronic circuitry including, for example, programmable logic circuitry, field-programmable gate arrays (FPGA), or programmable logic arrays (PLA) may execute the computer readable program instructions by utilizing state information of the computer readable program instructions to personalize the electronic circuitry, in order to perform aspects of the present invention. 
     Aspects of the present invention are described herein with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems), and computer program products according to embodiments of the invention. It will be understood that each block of the flowchart illustrations and/or block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams, can be implemented by computer readable program instructions. 
     These computer readable program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks. These computer readable program instructions may also be stored in a computer readable storage medium that can direct a computer, a programmable data processing apparatus, and/or other devices to function in a particular manner, such that the computer readable storage medium having instructions stored therein comprises an article of manufacture including instructions which implement aspects of the function/act specified in the flowchart and/or block diagram block or blocks. 
     The computer readable program instructions may also be loaded onto a computer, other programmable data processing apparatus, or other device to cause a series of operational steps to be performed upon the computer, other programmable apparatus or other device to produce a computer implemented process, such that the instructions which execute on the computer, other programmable apparatus, or other device implement the functions/acts specified in the flowchart and/or block diagram block or blocks. 
     The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods, and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of instructions, which comprises one or more executable instructions for implementing the specified logical function(s). In some alternative implementations, the functions noted in the blocks may occur out of the order noted in the Figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustration, and combinations of blocks in the block diagrams and/or flowchart illustration, can be implemented by special purpose hardware-based systems that perform the specified functions or acts or carry out combinations of special purpose hardware and computer instructions. 
     In  FIG. 1 , computer system  101  comprises a processor  103  coupled through one or more I/O Interfaces  109  to one or more hardware data storage devices  111  and one or more I/O devices  113  and  115 . 
     Hardware data storage devices  111  may include, but are not limited to, magnetic tape drives, fixed or removable hard disks, optical discs, storage-equipped mobile devices, and solid-state random-access or read-only storage devices. I/O devices may comprise, but are not limited to: input devices  113 , such as keyboards, scanners, handheld telecommunications devices, touch-sensitive displays, tablets, biometric readers, joysticks, trackballs, or computer mice; and output devices  115 , which may comprise, but are not limited to printers, plotters, tablets, mobile telephones, displays, or sound-producing devices. Data storage devices  111 , input devices  113 , and output devices  115  may be located either locally or at remote sites from which they are connected to I/O Interface  109  through a network interface. 
     Processor  103  may also be connected to one or more memory devices  105 , which may include, but are not limited to, Dynamic RAM (DRAM), Static RAM (SRAM), Programmable Read-Only Memory (PROM), Field-Programmable Gate Arrays (FPGA), Secure Digital memory cards, SIM cards, or other types of memory devices. 
     At least one memory device  105  contains stored computer program code  107 , which is a computer program that comprises computer-executable instructions. The stored computer program code includes a program that implements a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits in accordance with embodiments of the present invention, and may implement other embodiments described in this specification, including the methods illustrated in  FIGS. 1-2 . The data storage devices  111  may store the computer program code  107 . Computer program code  107  stored in the storage devices  111  is configured to be executed by processor  103  via the memory devices  105 . Processor  103  executes the stored computer program code  107 . 
     In some embodiments, rather than being stored and accessed from a hard drive, optical disc or other writeable, rewriteable, or removable hardware data-storage device  111 , stored computer program code  107  may be stored on a static, nonremovable, read-only storage medium such as a Read-Only Memory (ROM) device  105 , or may be accessed by processor  103  directly from such a static, nonremovable, read-only medium  105 . Similarly, in some embodiments, stored computer program code  107  may be stored as computer-readable firmware  105 , or may be accessed by processor  103  directly from such firmware  105 , rather than from a more dynamic or removable hardware data-storage device  111 , such as a hard drive or optical disc. 
     Thus the present invention discloses a process for supporting computer infrastructure, integrating, hosting, maintaining, and deploying computer-readable code into the computer system  101 , wherein the code in combination with the computer system  101  is capable of performing a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits. 
     Any of the components of the present invention could be created, integrated, hosted, maintained, deployed, managed, serviced, supported, etc. by a service provider who offers to facilitate a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits. Thus the present invention discloses a process for deploying or integrating computing infrastructure, comprising integrating computer-readable code into the computer system  101 , wherein the code in combination with the computer system  101  is capable of performing a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits. 
     One or more data storage units  111  (or one or more additional memory devices not shown in  FIG. 1 ) may be used as a computer-readable hardware storage device having a computer-readable program embodied therein and/or having other data stored therein, wherein the computer-readable program comprises stored computer program code  107 . Generally, a computer program product (or, alternatively, an article of manufacture) of computer system  101  may comprise the computer-readable hardware storage device. 
     While it is understood that program code  107  for a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits may be deployed by manually loading the program code  107  directly into client, server, and proxy computers (not shown) by loading the program code  107  into a computer-readable storage medium (e.g., computer data storage device  111 ), program code  107  may also be automatically or semi-automatically deployed into computer system  101  by sending program code  107  to a central server (e.g., computer system  101 ) or to a group of central servers. Program code  107  may then be downloaded into client computers (not shown) that will execute program code  107 . 
     Alternatively, program code  107  may be sent directly to the client computer via e-mail. Program code  107  may then either be detached to a directory on the client computer or loaded into a directory on the client computer by an e-mail option that selects a program that detaches program code  107  into the directory. 
     Another alternative is to send program code  107  directly to a directory on the client computer hard drive. If proxy servers are configured, the process selects the proxy server code, determines on which computers to place the proxy servers&#39; code, transmits the proxy server code, and then installs the proxy server code on the proxy computer. Program code  107  is then transmitted to the proxy server and stored on the proxy server. 
     In one embodiment, program code  107  for a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits is integrated into a client, server and network environment by providing for program code  107  to coexist with software applications (not shown), operating systems (not shown) and network operating systems software (not shown) and then installing program code  107  on the clients and servers in the environment where program code  107  will function. 
     The first step of the aforementioned integration of code included in program code  107  is to identify any software on the clients and servers, including the network operating system (not shown), where program code  107  will be deployed that are required by program code  107  or that work in conjunction with program code  107 . This identified software includes the network operating system, where the network operating system comprises software that enhances a basic operating system by adding networking features. Next, the software applications and version numbers are identified and compared to a list of software applications and correct version numbers that have been tested to work with program code  107 . A software application that is missing or that does not match a correct version number is upgraded to the correct version. 
     A program instruction that passes parameters from program code  107  to a software application is checked to ensure that the instruction&#39;s parameter list matches a parameter list required by the program code  107 . Conversely, a parameter passed by the software application to program code  107  is checked to ensure that the parameter matches a parameter required by program code  107 . The client and server operating systems, including the network operating systems, are identified and compared to a list of operating systems, version numbers, and network software programs that have been tested to work with program code  107 . An operating system, version number, or network software program that does not match an entry of the list of tested operating systems and version numbers is upgraded to the listed level on the client computers and upgraded to the listed level on the server computers. 
     After ensuring that the software, where program code  107  is to be deployed, is at a correct version level that has been tested to work with program code  107 , the integration is completed by installing program code  107  on the clients and servers. 
     Embodiments of the present invention may be implemented as a method performed by a processor of a computer system, as a computer program product, as a computer system, or as a processor-performed process or service for supporting computer infrastructure. 
       FIG. 2  is a flow chart that illustrates steps of a method for using direct sums and invariance groups to test partially symmetric quantum-logic circuits in accordance with embodiments of the present invention.  FIG. 2  shows elements identified by reference numbers  200 - 220 . 
     In step  200 , a processor of a quantum-logic test-development system receives a description of a quantum-logic circuit, or “q-module” with n inputs {x 1  . . . x n }, each of which may assume any oft states, and one output that can assume any of s states. The operation performed by this q-module can be expressed as a function f k ( x ) that maps each n-element input vector  x ={x 1 , . . . , x n } onto one of the s output states. 
     In one example, a two-input, one-output quantum circuit device has two inputs {x 1 , x 2 } that may each assume any of three states {0, 1, 2}. The circuit&#39;s output f( x ) may assume any of four states {0, 1, 2, 3}. In this example, n=2, t=4, and the set of all possible input vectors is {(00), (01), (02), (10), (11), (12), (20), (21), (22)}. 
     In another example, inputs {x1, x2, x3} of a 3-input, 1-output-state q-module with output that can assume any of s distinct states. The state of the three inputs are represented by an input vector x=(x1, x2, x3) and the values (or states) assumed by each input comprised by this vector may be subject to permutations that include (id), (12), (13), (23), (123), or (312). As described above, the inputs of the q-module may be reordered by permutations into any of six possible distinct orders: (x1, x2, x3), (x1, x3, x2), (x2, x1, x3), (x2, x3, x1), (x3, x1, x2), and (x3, x2, x1). 
     If the operation of the q-module can be represented by a function f(x) that maps each possible input vector x onto a corresponding value of s, one possible invariance group might contain a set of permutations {(1,2),(2,3)}, which correspond to input permutations (x2, x1, x3) and (x1, x3, x2). Because these permutations are invariant, swapping either the first two inputs {x1, x2} or the last two inputs {x2, x3} will not change the output of the q-module. For example, an input (010) would produce the same output as would inputs (100) (permutation (x1, x2)) and (001) (permutation (x2, x3)). 
     Because f(x1, x2, x3)=f(x2, x1, x3)=f(x1, x3, x2) in this example, it is possible to simultaneously test three input vectors by testing only one of them. 
     In step  205 , the system identifies a function f( x ) that represents the functionality performed by the q-module upon an n-tuple input vector  x  that represents an ordered set of n inputs of the q-module. The domain of function f consists of all inputs  x ={x1, x2, . . . , xn} of the q-module, and the value of any f(x1, x2, xn) is defined as an output state of q-module for input vector x=(x1, x2, xn). 
     Expressed more formally, the operation generated by a quantum module M can be represented by function f: {0, 1, . . . , t−1} n →{0, 1, . . . , s−1}, and the value of f(x 1 , x 2 , . . . , x n ) is the output produced by M in response to receiving input vector  x =(x 1 , x 2 , . . . , x n ). The set S(f) of all possible permutations of M&#39;s inputs that do not change the output of M is called an invariance group, or a symmetry group, of f( x ). 
     This may be stated as:
         f: {0, 1, . . . , t−1} n →{ 0 ,  1 , . . . , s−1}, where t&gt;1, s&gt;1.   σ is a permutation comprised by symmetric group S n , where S n  contains permutations of indexes of input vector  x =(x 1 , x 2 , . . . , x n ).   The action of permutation σ on f(x 1 , x 2 , . . . , x n ) may be expressed as:   f σ (x 1 , x 2 , . . . , x n )=f(x σ(1) , x σ(2) , . . . , x σ(n) ). That is, applying function f σ  to an input vector  x  is equivalent to applying function f( x ) to an input vector  x   σ ={x σ(1) , x σ(2) , . . . , x σ(n) },
           where  x   σ =a permuted set of inputs created by applying permutation σ to  x .   
           S(f)={σϵSn:f=f σ }. That is, S(f) is the set of all permutations σ that, when performed upon an input vector  x , do not change the output value of f( ).   The set of permutations S(f) is thus the invariance group, or symmetry group of f( ).       

     In step  210 , the system divides the q-module&#39;s n inputs {x 1  . . . x n } into k subsets by any means known in the art. This division may be performed as a function of the architecture of the q-module and, in many cases, a person skilled in the art may identify logical split points that divide the inputs by referring to product documentation published by the manufacturer of the q-module. 
     The examples described here refer to this set of k subsets as {A i }, i=1, 2, . . . k. The total number of inputs in an i th  subset is represented as |A i |=n i , where (n 1 +n 2 + . . . n k )=n (the total number of inputs). In other words, every input of the q-module is contained in one and only one of k mutually exclusive, or disjoint, subsets A i . 
     Subsequent steps of  FIG. 2  will consider only permutations that preserve the division of inputs into subsets {A i }. That is, each permutation will permute only inputs that are in the same subset. None will permute inputs from more than one subset. 
     In step  215 , the system identifies an invariance group of function f( ) as a direct sum of a set of groups that each comprise one of the subsets identified in step  210 . Here, each group can be expressed as (G,X), where X is a subset of inputs and G is a set of permutations that may be performed upon the inputs comprised by X. If, for example, three subsets A 1 , A 2 , and A 3 , were identified in step  210 , the system here creates three sets of permutation operations G 1 , G 2 , and G 3 , each of which comprises a set of permutations that may be performed upon inputs comprised by one of the three subsets. The system then generates three groups (G 1 ,A 1 ), (G 2 ,A 2 ), and (G 3 ,A 3 ), where each {G 1 } is a set of permutations of inputs of a corresponding subset Ai. The system generates the invariance group as the direct sum:
 
( G   1   ,A   1 )⊕( G   2   ,A   2 )⊕( G   3   ,A   3 ).
 
     As used here, the direct sum operator ⊕ generates an output group as a function of two or more input groups. Consider, for example, a case in which the system in step  210  divided a q-module&#39;s n inputs into two subgroups A 1  and A 2 , where A 1  contains n1 inputs, A 2  contains n2 inputs, and n1+n2=n. 
     This may be expressed by the statements:
 
 A   1   ={x   1    . . . x   n1 },
 
 A   2   ={x   n1+1    . . . x   n },
 
| A   1   |=n 1, and
 
| A   2   |=n 2.
 
     If G represents all possible permutations of subset A 1 &#39;s inputs {x 1  . . . x n1 } and H represents all possible permutations of subset A 2 &#39;s inputs {x n1+1  . . . x n }, the two subsets, along with their permutations, may be represented as a pair of permutation groups (G, A 1 ) and (H, A 2 ). 
     The direct sum of (G, A 1 ) and (H, A 2 ), represented as G⊕H, can then be derived by Equation (1):
 
 G⊕H =( G     H,A   1   ∪A   2 )  (1)
 
     where   is the Cartesian coordinate vector operator and ∪ is the set-union operator. 
     An intrinsic characteristic of this usage of the direct-sum function is the fact that the above computation does not generate permutations of inputs comprised by two distinct subsets. That is, G⊕H identifies permutations of inputs contained in either A 1  or A 2 , but does not identify permutations that swap an input comprised by a first subset A 1  with an input comprised by a second subset A 2 . As a result, no permutation produced by direct sum G⊕H can shift an input from one subset to the other. 
     If, for example, G comprises permutations of a subset A 1  that consists of inputs {1, 2, 3}, and H comprises permutations of a subset A 2  that consists of inputs {4, 5, 6}, then G⊕H could produce permutations that comprise:
         a permutation of inputs comprised by A 1 , such as (1,2) (exchange inputs 1 and 2, but leave inputs 3, 4, 5, and 6 unchanged) or (2,3) (exchange inputs 2 and 3, but leave inputs 1, 4, 5, and 6 unchanged); or   a permutation of inputs comprised by A 2 , such as (4,5) (exchange inputs 4 and 5, but leave inputs 1, 2, 3, and 6 unchanged) or (5,6) (exchange inputs 5 and 6, but leave inputs 1, 2, 3, and 4 unchanged);       

     In no case, however, could G⊕H generate permutations that mix inputs of A 1  with inputs of A 2 , such as (1, 2, 6) or (4, 5, 3). 
     This computation may be generalized to cases that comprise more than two subgroups or divisions of a q-module&#39;s n inputs. If, for example, a q-module&#39;s inputs are represented as an n-element vector  x =(x 1  . . . x n ), each group of permutations G would operate on a mutually exclusive subset of  x , such that every input of  x  is contained in one and only one of the mutually exclusive subsets of  x . 
     For every set of inputs  x ={x 1 , x 2 , . . . x n } and every method of division of those inputs into of k subsets {A i } there exists a function f k ( x ) such that S(f k ) (the invariance group of f k ( )) is a direct sum of permutation groups that each act on one of the subsets A i . 
     This function f k ( x ) may be represented by Equation (2), where 0 n  represents a string of n inputs in a 0 state and 1 n  represents a string of n inputs in a 1 state. Here  x   1  is a vector of length (n 1 + . . . +n k−1 ) and  x   2  is a vector of length n k . As in previous examples, | x |=n=(n 1 +n 2 )=(n 1 + . . . +n k ). 
     
       
         
           
             
               
                 
                   
                     
                       f 
                       k 
                     
                     ⁡ 
                     
                       ( 
                       
                         x 
                         _ 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             0 
                             , 
                           
                         
                         
                           
                               
                             ⁢ 
                             
                               
                                 x 
                                 _ 
                               
                               = 
                               
                                 
                                   
                                     x 
                                     _ 
                                   
                                   1 
                                 
                                 ⁢ 
                                 
                                   0 
                                   
                                     n 
                                     k 
                                   
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 f 
                                 
                                   k 
                                   - 
                                   1 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   x 
                                   _ 
                                 
                                 ) 
                               
                             
                             , 
                           
                         
                         
                           
                               
                             ⁢ 
                             
                               
                                 x 
                                 _ 
                               
                               = 
                               
                                 
                                   
                                     x 
                                     _ 
                                   
                                   1 
                                 
                                 ⁢ 
                                 
                                   1 
                                   
                                     n 
                                     k 
                                   
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             1 
                             , 
                           
                         
                         
                           
                               
                             ⁢ 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 = 
                                 
                                   
                                     0 
                                     
                                       
                                         n 
                                         1 
                                       
                                       + 
                                       
                                         n 
                                         2 
                                       
                                       + 
                                       … 
                                       + 
                                       
                                         n 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       x 
                                       _ 
                                     
                                     2 
                                   
                                 
                               
                               , 
                               
                                 
                                   
                                     x 
                                     _ 
                                   
                                   2 
                                 
                                 ≠ 
                                 
                                   0 
                                   
                                     n 
                                     k 
                                   
                                 
                               
                               , 
                               
                                 1 
                                 
                                   n 
                                   k 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             0 
                             , 
                           
                         
                         
                           
                               
                             ⁢ 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 = 
                                 
                                   
                                     1 
                                     
                                       
                                         n 
                                         1 
                                       
                                       + 
                                       
                                         n 
                                         2 
                                       
                                       + 
                                       … 
                                       + 
                                       
                                         n 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                   ⁢ 
                                   
                                     
                                       x 
                                       _ 
                                     
                                     2 
                                   
                                 
                               
                               , 
                               
                                 
                                   
                                     x 
                                     _ 
                                   
                                   2 
                                 
                                 ≠ 
                                 
                                   0 
                                   
                                     n 
                                     k 
                                   
                                 
                               
                               , 
                               
                                 1 
                                 
                                   n 
                                   k 
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             0 
                             , 
                           
                         
                         
                           
                               
                             ⁢ 
                             Otherwise 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     Here, function f k ( x ) (the operation performed by a q-module on vector  x , where an input vector  x  has been divided into k subsets) returns a value of 0 or 1. This function is semi-recursive because in some cases, its output is determined by recursively calling the same function f( ) for any k−1 subsets of the k subsets). 
     In this example:
         if input vector  x  comprises any n 1  input states followed by n k  ZERO states, f k ( x )=0   if  x  comprises any n 1  input states followed by n k  ONE states, then f k ( x )=a value derived by semi-recursively calling f k−1 ( x )   if  x  comprises any (n 1 +n 2 + . . . +n k−1 ) ZERO states, followed by any n 2  input states that are neither all ZERO states nor all ONE states, then f k ( x )=1   if  x  comprises any (n 1 +n 2 + . . . +n k−1 ) ONE states, followed by any n 2  input states that are neither all ZERO states nor all ONE states, then f k ( x )=0   otherwise f k ( x )=0.       

     In a simple example, consider the case where k=2 (that is, where the input vector of the q-module was divided into two subvectors  x 1    and  x 2    in step  210 ), where | x 1   |=n 1 , | x 2   |=n 2 , and | x |=(n 1 +n 2 )=n, the total number of inputs. In this example, we arbitrarily derive an output value of f k−1 ( x ) to be equal to 1. 
     This yields: 
     
       
         
           
             
               
                 f 
                 1 
               
               ⁡ 
               
                 ( 
                 
                   x 
                   _ 
                 
                 ) 
               
             
             = 
             1 
           
         
       
       
         
           
             
               
                 f 
                 2 
               
               ⁡ 
               
                 ( 
                 
                   x 
                   _ 
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         
                           0 
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           
                             
                               x 
                               _ 
                             
                             = 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 0 
                                 
                                   n 
                                   2 
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           
                             
                               f 
                               1 
                             
                             ⁡ 
                             
                               ( 
                               
                                 x 
                                 _ 
                               
                               ) 
                             
                           
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           
                             
                               x 
                               _ 
                             
                             = 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 1 
                                 
                                   n 
                                   2 
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           1 
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 x 
                                 _ 
                               
                               = 
                               
                                 
                                   0 
                                   
                                     n 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     x 
                                     _ 
                                   
                                   2 
                                 
                               
                             
                             , 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 2 
                               
                               ≠ 
                               
                                 0 
                                 
                                   n 
                                   2 
                                 
                               
                             
                             , 
                             
                               1 
                               
                                 n 
                                 2 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           0 
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 x 
                                 _ 
                               
                               = 
                               
                                 
                                   1 
                                   
                                     n 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     x 
                                     _ 
                                   
                                   2 
                                 
                               
                             
                             , 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 2 
                               
                               ≠ 
                               
                                 0 
                                 
                                   n 
                                   2 
                                 
                               
                             
                             , 
                             
                               1 
                               
                                 n 
                                 2 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           0 
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           Otherwise 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       f 
                       2 
                     
                     ⁡ 
                     
                       ( 
                       
                         x 
                         _ 
                       
                       ) 
                     
                   
                 
                 = 
                 
                   { 
                   
                     
                       
                         
                           0 
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           
                             
                               x 
                               _ 
                             
                             = 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 0 
                                 
                                   n 
                                   2 
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           1 
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           
                             
                               x 
                               _ 
                             
                             = 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 1 
                               
                               ⁢ 
                               
                                 1 
                                 
                                   n 
                                   2 
                                 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           1 
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 x 
                                 _ 
                               
                               = 
                               
                                 
                                   0 
                                   
                                     n 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     x 
                                     _ 
                                   
                                   2 
                                 
                               
                             
                             , 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 2 
                               
                               ≠ 
                               
                                 0 
                                 
                                   n 
                                   2 
                                 
                               
                             
                             , 
                             
                               1 
                               
                                 n 
                                 2 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           0 
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           
                             
                               
                                 x 
                                 _ 
                               
                               = 
                               
                                 
                                   1 
                                   
                                     n 
                                     1 
                                   
                                 
                                 ⁢ 
                                 
                                   
                                     x 
                                     _ 
                                   
                                   2 
                                 
                               
                             
                             , 
                             
                               
                                 
                                   x 
                                   _ 
                                 
                                 2 
                               
                               ≠ 
                               
                                 0 
                                 
                                   n 
                                   2 
                                 
                               
                             
                             , 
                             
                               1 
                               
                                 n 
                                 2 
                               
                             
                           
                         
                       
                     
                     
                       
                         
                           0 
                           , 
                         
                       
                       
                         
                             
                           ⁢ 
                           Otherwise 
                         
                       
                     
                   
                 
               
             
           
         
       
     
     In this simple two-state example:
         if input vector  x  consists of any n 1  input states followed by n 2  ZERO states, f 2 (x)=0   if  x  consists of any n 1  states followed by n 2  ONE states, then f 2 (x)=f 1 (x)=1, a value derived by semi-recursively calling f k−1 (x)   if  x  consists of any n 1  ZERO states, followed by any n 2  input states that are neither all ZERO states nor all ONE states, then f 2 (x)=1   if  x  consists of any n 1  ONE states, followed by any n 2  input states that are neither all ZERO states nor all ONE states, then f 2 (x)=0   otherwise f 2 ( x )=0.       

     In step  220 , the system uses the functions and invariance group derived in step  215  as the direct sums of the subsets identified in step  215  to streamline the testing of the q-module. This invariance group specifies a set of invariant or symmetrical permutations that, when performed upon the q-module&#39;s inputs, do not cause the q-module&#39;s output to change. 
     Consider a simple example in which a q-module has four inputs {x1, x2, x3, x4}, that are divided in step  210  into two subsets (x1,x2) and (x3,x4). The direct sum of these two groups, as computed by Equation (1), yields an invariance group that comprises four permutations, including the trivial-case identity permutation (id), which specifies that no inputs are permuted:
 
{( id ),(1,2),(3,4),(1,2)(3,4)}
 
     This invariance group indicates that the output of the q-module does not change when:
         input x1 is exchanged with input x2,   input x3 is exchanged with input x4, or   x1 is exchanged with x2 and x3 is exchanged with x4.       

     Permutations comprised by the previously identified invariance group may be used to identify certain input vectors  x  of the q-module that do not need to be tested. Because permuting the q-module&#39;s input vectors by means of a permutation of the invariance group does not change the q-module&#39;s output, once one input vector has been tested, it is not necessary to test any other vectors that may be derived by performing invariant permutations upon the previously tested vector. 
     This increased test efficiency is illustrated in Table 1 below, which is based on the previous 4-input/2-state example, in which an invariance group consists of the set of permutations:
 
 S ( f )={( id ),(1,2),(3,4),(1,2)(3,4)}
 
     Here, permutation (x1,x2) specifies that permuting the states of the first two inputs of the q-module does not change the output state of the q-module. Therefore, there is no need to test any input vector  x  that differs from a previously verified input vector  x  only in the order of the states of the first two inputs. For example, if the q-module is known to produce correct output in response to input vector  x =(1, 0, 1, 1), it is not necessary to test the operation of the q-module when input  x  is permuted to (0, 1, 1, 1). 
     Table 1 illustrates an example of how a q-module test procedure may be optimized by considering the four-permutation invariance group enumerated above:
 
 S ( f )={( id ),(1,2),(3,4),(1,2)(3,4)}
 
     Here, once input vector (0, 1, 1, 0) has been verified, there is no need to test the following permutations: 
     (0, 1, 1, 0) (the trivial (id) permutation) 
     (1, 0, 1, 0) (permutation (1,2): swap 1 with 2) 
     (0, 1, 0, 1) (permutation (3,4): swap 3 with 4); and 
     (1, 0, 0, 1) (permutation (1,2) (3,4): swap 1 with 2 and swap 3 with 4) 
     Table 1 illustrates this example for all possible values of input vector x of the four-input, two-state q-module. The first four columns identify all possible input states identified by 4-tuple input vector  x , which represents inputs that may be received by the q-module. The fifth column identifies whether a test procedure is required to verify the output produced by function f 2 ( x ), which defines the expected operation of the q-module, for each possible value of input vector  x . Permutations of previously verified vectors  x  that do not need to be tested are identified by the term “NOTEST.” 
     
       
         
           
               
               
               
               
               
             
               
                 TABLE 1 
               
               
                   
               
               
                 x1 
                 x2 
                 x3 
                 x4 
                 f 2 (x1, x2, x3, x4) 
               
               
                   
               
             
            
               
                 0 
                 0 
                 0 
                 0 
                 TEST 
               
               
                 0 
                 0 
                 0 
                 1 
                 TEST 
               
               
                 0 
                 0 
                 1 
                 0 
                 NOTEST 
               
               
                 0 
                 0 
                 1 
                 1 
                 TEST 
               
               
                 0 
                 1 
                 0 
                 0 
                 TEST 
               
               
                 0 
                 1 
                 0 
                 1 
                 TEST 
               
               
                 0 
                 1 
                 1 
                 0 
                 NOTEST 
               
               
                 0 
                 1 
                 1 
                 1 
                 TEST 
               
               
                 1 
                 0 
                 0 
                 0 
                 NOTEST 
               
               
                 1 
                 0 
                 0 
                 1 
                 NOTEST 
               
               
                 1 
                 0 
                 1 
                 0 
                 NOTEST 
               
               
                 1 
                 0 
                 1 
                 1 
                 NOTEST 
               
               
                 1 
                 1 
                 0 
                 0 
                 TEST 
               
               
                 1 
                 1 
                 0 
                 1 
                 TEST 
               
               
                 1 
                 1 
                 1 
                 0 
                 NOTEST 
               
               
                 1 
                 1 
                 1 
                 1 
                 TEST 
               
               
                   
               
            
           
         
       
     
     In a similar manner, an invariance group may be used to reduce the total number of tests required to completely verify other q-modules. In the above 4-input, 2-output-state example, the total number of tests is reduced from 16 to 9, but when the number of inputs or the number of input or output states of a q-module increases, embodiments of the present invention may allow very large numbers of tests to be eliminated. 
     For example, if a q-module has 10 inputs {x1 . . . x10} divided into k=2 subsets A 1 ={x1, x2, . . . , x5} and A 2 ={x6, x7, . . . , x10}, a symmetry group can be derived as a direct sum of two groups. Instead of requiring 2 10 =1024 tests, embodiments of the present invention would allow the q-module to be fully verified with only 36 sets of input values. 
     Similarly, if a q-module has 100 inputs divided into k=2 subsets {x1, x2, . . . , x50} and {x51, x52, . . . , x100}, an invariance group could be generated as the group of all permutations of these two input subsets. Here, instead of requiring 2 100  tests to completely verify the circuit, embodiments of the present invention would require only 2601 values. 
     These reductions in the number of required tests can be generalized. Methods of the present invention may, for example, use group theory to determine whether f( x ) is invariant under S({1, 2, . . . , n})⊕S({n+1, n+2, . . . , 2n}) where S( x n   ) is a group of all permutations of an input subset  x n   . If S(f) creates a group S({1, 2, . . . , n}), the generators of that group are can be determined, through means known in the art, to be permutations (1, 2) and (1, 2, . . . , n). Determining whether f( ) is invariant under S({1, 2}) requires evaluation of two conditions, and determining whether f( ) is invariant under S({1, 2, . . . , n})⊕S({n+1, n+2, . . . , 2n}) requires evaluation of only four conditions, rather than (2n)! conditions. 
     This maybe expressed formally for any q-module and function f( ). If S(f) is direct sum of groups {(G 1 , A 1 ), (G 2 , A 2 ), . . . , (G k , A k )}, then the q-module may be fully tested by testing only permutations {(1, 2), (1, 2, . . . , n 1 ), (n 1 +1, n 1 +2), (n 1 +1, n 1 +2, . . . , n 1 +n 2 ), (n 1 +n 2 + . . . +n k−1 +1, n 1 +n 2 + . . . +n k−1 +2), (n 1 +n 2 + . . . +n k−1 +1, n 1 +n 2 + . . . +n k−1 +2, . . . , n)}.