This is a ridiculously open-ended spec, and there's a mountain of federal legislation to comply with. I might go as far as to say that it's a reckless way to try to procure software, as it's very much a product which needs to work and be supported over the long term, not some sort of black-box AI quick win.
To which legislation in particular are you referring? I often see this claim on HN, but I do not think that most people here have any real understanding of the situation. As an anecdote, I work on a medical information system for emergency rooms. The VA uses our system in some locations. Federal regulations are not at all onerous. Things like HIPAA are dealt with using a few really basic rules.
Besides HIPAA, it is possible this software would need to comply with the VA's "6500", their internal information security handbook, as well as meeting relevant FISMA / NIST requirements (see http://csrc.nist.gov/groups/SMA/fisma/index.html ).